Java merge sort implementation

Question

Is this a good implementation?

static int[] mergeSort(int[] arr) { if (arr.length <= 1) { return arr; } int[] left, right; left = Arrays.copyOfRange(arr, 0, arr.length / 2); right = Arrays.copyOfRange(arr, arr.length / 2, arr.length); left = mergeSort(left); right = mergeSort(right); return merge(left, right, arr); } private static int[] merge(int[] left, int[] right, int result[]) { int i = 0, j = 0, z = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result[z++] = left[i++]; } else { result[z++] = right[j++]; } } while (i < left.length) { result[z++] = left[i++]; } while (j < right.length) { result[z++] = right[j++]; } printArr(result); return result; } 

Answer 1

1

while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result[z++] = left[i++]; } else { result[z++] = right[j++]; } } while (i < left.length) { result[z++] = left[i++]; // Why empty line right here?? } while (j < right.length) { result[z++] = right[j++]; } 

You should not have an empty line before a closing brace, but you should have one immediately after a closing brace, so you should rewrite this to

while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result[z++] = left[i++]; } else { result[z++] = right[j++]; } } while (i < left.length) { result[z++] = left[i++]; } while (j < right.length) { result[z++] = right[j++]; } 

2

Add public before static int[] mergeSort(int[] arr) since you possibly want to expose your sort outside the current package.

3

In JDK, the convention is that all sort class methods do not return the array (they all are declared void) but modify the contents of the input array.

4

Your implementation allocates \$\mathcal{O}(n \log n)\$ worth memory, whereas a linear space complexity suffices if you do a little trick (see Summa summarum). This slows down your algorithm since asking for memory is expensive, plus whenever we lose all references to an array, the garbage collector has to do additional work behind the scene in order to deallocate it.

What happens there, is that we allocate an auxiliary copy of the input array only once. Then, we distinguish two array roles: source anb target. Whenever merging, we read the data from source and put in sorted order to target. The actual mergesort routine alternates the roles of the arrays at each particular recursion level. This eliminates copying stuff in the merging routine, which increases performance.

Summa summarum

All in all, I had this in mind (rename if needed):

public static void coderoddeMergesort(final int[] array) { coderoddeMergesort(array, 0, array.length); } public static void coderoddeMergesort(final int[] array, final int fromIndex, final int toIndex) { if (fromIndex > toIndex) { throw new IllegalArgumentException( "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } final int rangeLength = toIndex - fromIndex; if (rangeLength < 2) { // Trivially sorted. return; } // Allocate the auxiliary buffer only ONCE. final int[] aux = Arrays.copyOfRange(array, fromIndex, toIndex); // Do actual sorting. coderoddeMergesortImpl(aux, array, 0, rangeLength, fromIndex, toIndex); } private static void coderoddeMergesortImpl(final int[] source, final int[] target, final int sourceFromIndex, final int sourceToIndex, final int targetFromIndex, final int targetToIndex) { final int rangeLength = sourceToIndex - sourceFromIndex; if (rangeLength < 2) { return; } final int sourceMiddleIndex = sourceFromIndex + (rangeLength >>> 1); final int targetMiddleIndex = targetFromIndex + (rangeLength >>> 1); coderoddeMergesortImpl(target, source, targetFromIndex, targetMiddleIndex, sourceFromIndex, sourceMiddleIndex); coderoddeMergesortImpl(target, source, targetMiddleIndex, targetToIndex, sourceMiddleIndex, sourceToIndex); coderoddeMerge(source, target, targetFromIndex, sourceFromIndex, sourceMiddleIndex, sourceToIndex); } private static void coderoddeMerge(final int[] source, final int[] target, int targetOffset, int left, int right, final int rightBound) { final int leftBound = right; while (left < leftBound && right < rightBound) { target[targetOffset++] = source[left] < source[right] ? source[left++] : source[right++]; } System.arraycopy(source, left, target, targetOffset, leftBound - left); System.arraycopy(source, right, target, targetOffset, rightBound - right); } 

(You can find a complete performance demonstration here.)

The performance figures are as follows:

coderoddeMergesort() in 1100 milliseconds. mergeSort() in 1412 milliseconds. Arrays are same: true

Hope that helps.

Answer 2

 static int[] mergeSort(int[] arr) { 

If you want to call it array, please go ahead and write out the name.

Personally, I'd prefer data or numbers as names, but that may just be me.

 int[] left, right; left = Arrays.copyOfRange(arr, 0, arr.length / 2); right = Arrays.copyOfRange(arr, arr.length / 2, arr.length); 

While this will work, consider

 int[] left = Arrays.copyOfRange(arr, 0, arr.length / 2); int[] right = Arrays.copyOfRange(arr, arr.length / 2, arr.length); 

It's actually slightly shorter in this case, as int[] is shorter than left, right;. But even if it were longer, it is easier to follow with the declaration and initialization on the same line.

 int midpoint = arr.length / 2; 

This could make it clearer why you are passing around arr.length / 2 if you replace occurrences with midpoint.

 int i = 0, j = 0, z = 0; 

I would find this easier to read as either

 int i = 0, j = 0, z = 0; 

or

 int i = 0; int j = 0; int z = 0; 

One initialization per line.

 printArr(result); 

This looks like debugging code to me. If so, it should have been removed before review.

I don't have any real comments on the algorithm itself beyond what people said in the comments. You might be able to bring down the memory usage if you tried hard enough, but it shouldn't generally matter. This is a more elegant version and less susceptible to bugs if you aren't memory bound.

You may be doing this just as an exercise (you can use the reinventing-the-wheel tag to indicate this) or for some other reason. In practice, the standard Arrays.sort implementation is good enough for most needs. You wouldn't normally need to roll your own.

Answer 3

A properly implemented Mergesort takes \$O(n \log n)\$ time and uses \$O(n)\$ extra memory. And while I think your code complies with those limits, the constants involved, especially when it comes to memory, are larger than needed

You typically want to write your algorithm to sort in-place (and precede it with a copy if you don't want to alter the input). This spares you lots of data copying ,which now only needs to happen in the merge step, and you actually only need to copy to a separate buffer the first half of the array. This also means that, once the merging is finished, any remaining items on the right side are already in the correct location and do not need to be copied back to the output.

I'm not sure if the written description is helping or just making things more confusing, so let me explain it in code:

static int[] mergeSort(int[] array) { int[] sortedArray = Arrays.copyOf(array, array.length); mergeSort(sortedArray, 0, sortedArray.length); return sortedArray; } private static void mergeSort(int[] array, int from, int to) { int midpoint = from + (to - from) / 2; if (to - from > 2) { mergeSort(array, from, midpoint); mergeSort(array, midpoint, to); } merge(array, from, midpoint, to); } private static void merge(int[] array, int from, int midpoint, int to) { int[] tmp = Arrays.CopyOfRange(array, from, midpoint); int readLeftIndex = 0; int readRightIndex = midpoint; int writeIndex = from; while(readLeftIndex < tmp.length() && readRightIndex < to) { if (array[readRightIndex] < tmp[readLeftIndex]) { array[writeIndex++] = array[readRightIndex++]; } else { array[writeIndex++] = tmp[readLeftIndex++]; } } while (readLeftIndex < tmp.length()) { array[writeIndex++] = tmp[readLeftIndex++]; } } 

Further optimizations would include allocating a single buffer of size array.length / 2 at the top level function and pass it around to avoid repeated allocations, but that would probably take away from readability, so am skipping it here.