[Java] Mergesort sorting algorithm for int arrays

Mergesort is well known as one of the best sorting algorithms out there with a O(n log n) worst case runtime; it doesn't get much better than this without strange big-O tricks.

But while understanding how it works is easy, implementing it is a different story given that it combines two nested function calls in the recursion and requires careful array index management. Also Java pass by value adds a small gotcha for good measure.

You can find my implementation for int[] arrays (as in: not Integer, not ArrayList, not List, not whatever else. Pure and simple int primitive data type with old fashioned array, the kind that does not change size once created if you can still remember those) on my Gist along with some test cases.

As for caveats, visualising the method is easy after the basic handling (null, one element): break the array in two halves, if it's odd length, one will be bigger, no problem. Keep breaking it until you only have one element in each half; that one is sorted, great. Now merge the two halves and keep going up until you rebuilt the whole array.

What to watch out for:

• No single recursion by calling the same single method over and over until the base case! You have recursion going down with a function (sort) that keeps breaking the array in half then you go up calling a function (merge) that merges the two halves together while sorting them
• CAREFUL INDEX MANAGEMENT! So easy to screw up. Since you don't know how the two halves are sorted you cannot assume you can loop from 0 to Math.min(left.length, right.length) thinking you won't go out of bounds like this while still comparing all elements properly. You cannot go out of bounds anyway if you loop on two indexes at the same time! You must move up the two arrays independently while comparing all elements in pairs, that's not achievable with a single index!
• Finishing the above loop is NOT the end. You can have leftovers on either array (only one!), so remember to finish that up by copying all remaining elements in place in a separate loop
• Java pass by value means the input you receive (array to sort) has to be brought around the whole operation. Also if you create a new array in merge, you will lose it during recursion because its reference would be local, not tied to some upper level variable and therefore all the good work you will do on it will be lost as soon as the function returns! This last part comes almost naturally anyway while writing the code the moment you go through it and realise that the recursion is not really using the local variable at all