Merge sort implementation and improvements

Question

I would like your opinion on my Java implementation of the merge sort algorithm on an integer array, since I'm not really into algorithms I'd like to know from you if this is a correct implementation and if it can be improved somehow.

For example, it requires a lot of space for the sub arrays, but this should be normal for the merge sort as it is not space constant. I tested it and it seems to work.

private int[] mergeSort(int[] array) {
 if (array.length == 1) return array;
 int start = 0;
 int end = array.length;
 int middle = (end-start)/2;
 int[] left = Arrays.copyOfRange(array, start, middle);
 int[] right = Arrays.copyOfRange(array, middle, end);
 int[] sortedLeft = mergeSort(left);
 int[] sortedRight = mergeSort(right);
 return merge(sortedLeft, sortedRight);
}
private int[] merge(int[] first, int[] second) {
 int[] result = new int[first.length + second.length];
 int posFirst = 0;
 int posSecond = 0;
 int resultPos = 0;
 while (resultPos < result.length) {
 if (posFirst == first.length) {
 result[resultPos++] = second[posSecond++];
 }
 else if (posSecond == second.length) {
 result[resultPos++] = first[posFirst++];
 }
 else if (first[posFirst] > second[posSecond]) {
 result[resultPos++] = second[posSecond++];
 } else {
 result[resultPos++] = first[posFirst++];
 }
 }
 return result;
}

Answer 1

MergeSort is a nice sort algorithm because the concepts are relatively simple, even the recursion makes sense, and it all just 'fits'.

You have done a good job at describing the algorithm through your code. Putting performance aside, I think you did a good job. Small items to consider:

1. the methods do not use any instance state information, so they should probably both be static methods, and should the main mergeSort method there be public too?

2. The last two conditions in the cascading if/else statement are:

    else if (first[posFirst] > second[posSecond]) {
    result[resultPos++] = second[posSecond++];
    } else {
    result[resultPos++] = first[posFirst++];
    }
   

   I would prefer to see the logic a bit clearer in the sense that first should be handled first, and it can be done like:

   else if (first[posFirst] <= second[posSecond]) {
    result[resultPos++] = first[posFirst++];
   } else {
    result[resultPos++] = second[posSecond++];
   }
   

3. One final nit-pick, you have posFirst, and posSecond, but then you called the other position resultPos? Shouldn't that be posResult?

As for the performance, your system creates many new arrays. Even though the logic of the sort algorithm is very apparent the way you have done it, the reality is that performance can be improved massively by creating one large temporary array and performing the merge in small parts from the source array, to the temp array, then swapping them to do the next larger merge.

Wikipedia has an algorithm written in C that does the bottom-up merge sort using two arrays, one is a temp array. Now that you have the algorithm done I encourage you to do a better implementation of the Wikipedia's code.... it is really ugly, and could do with a review ;-)

Answer 2

one of the things you can do is pass in the original array to merge and use that as result:

 return merge(sortedLeft, sortedRight, array);
}

and

private int[] merge(int[] first, int[] second, int[] result) {
 int posFirst = 0;
 int posSecond = 0;
 int resultPos = 0;

This reduces the space needed during the merge portion. Though at the cost of modifying the array the user put in.

Answer 3

I want to point out that you've made a fairly common "mistake" that could rear its ugly head if you decided to transition this code to bottom-up, for instance.

Your midpoint is calculated incorrectly:

int middle = (end-start)/2;

It should be:

int middle = (end+start)/2;

• rolfl: Good spotting there. I wonder if this is a partial copy/paste problem from the 'famous' bug which is solved with: start + (end - start)/2 : Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken
• Francesco Rigoni: Ok thank you, I didn't know about this bug but it makes a lot of sense now.