This is a specific case in merge sort. I'm trying to do a merge sort on an array that's created using the Java Integer
class. My implementation is slow and therefore needs some modifications for better performance. I believe the process where I copy the original items to two new arrays over and over again is slowing it down.
How do I merge sort without copying? The sorting must be stable and both methods should return Integer[]
.
private static Integer[] mergeSort(Integer[] a, int p, int q)
{
if (a.length <= 1) return a;
int mid = (int)Math.floor((q-p)/2);
Integer[] left = new Integer[(mid - p) + 1];
Integer[] right = new Integer[q - mid];
int index = 0;
for (int i = 0; i < left.length; i++)
{
left[i] = a[index++];
}
for (int i = 0; i < right.length; i++)
{
right[i] = a[index++];
}
left = mergeSort(left, 0, left.length-1);
right = mergeSort(right, 0, right.length-1);
return merge(left, right);
}
private static Integer[] merge(Integer[] a, Integer[] b)
{
int i = 0; int j = 0; int k = 0;
Integer[] result = new Integer[a.length+b.length];
while (i < a.length || j < b.length)
{
if (i != a.length && j != b.length)
{
if (a[i].compareTo(b[j]) <= 0)
{
result[k++] = a[i++];
}
else
{
result[k++] = b[j++];
}
}
else if (i < a.length)
{
result[k++] = a[i++];
}
else if (j < b.length)
{
result[k++] = b[j++];
}
}
return result;
sort(T[] a, Comparator<? super T> c)
, then it is mergesort (just checked). You only need to provide an implementation ofComparable<Integer>
, which should be trivial. \$\endgroup\$ – Jakub Zaverka Mar 22 '12 at 23:52