Merge Sort most efficient implementation

The following program is translated from C++ example given in Robert Sedgewick's Algorithms in C++, Parts 1-4

It introduces one type of improvement. It does a single copy of the whole sorting array into a an auxiliary array that is further dealt with. Next, the recursion splitting is done on the auxiliary array by alternating between the auxiliary array and original array so that the extra copying operation of the merged arrays doesn’t happen. Basically, the algorithm switches the role of the input and auxiliary array in each recursive call. For example, conceptually:

Regular Mergesort:

--merge

(((8) (5))((2) (3)))(((1) (7))((4) (6)))(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))-- copy back and ignore previous (UNNECESSARY)(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))

– – – – – – – –

This program:

--merge

(((8) (5))((2) (3)))(((1) (7))((4) (6)))(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))

--merge backwards

( 2 3 5 8 )( 1 4 6 7 )(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 )) 

Also, after splitting the array into halves gives small enough arrays, the algorithm uses insertion sort since it performs better on small data sets than merge sort. The threshold for when exactly to use insertion sort can be determined with trial-and-error.

The code:

static int M = 10;//insertion sort to be used once the mergesort partitions become small enoughstatic void insertionsort(int[] a, int l, int r) {int i, j, temp;for (i = 1; i < r + 1; i++) {temp = a[i];j = i;while ((j > 0) && a[j - 1] > temp) {a[j] = a[j - 1];j = j - 1;}a[j] = temp;}}//standard merging two sorted half arrays into single sorted arraystatic void merge(int[] merged_a, int start_a, int[] half_a1, int start_a1, int size_a1, int[] half_a2, int start_a2, int size_a2) {int i, j, k;int total_s = size_a1 + size_a2;for (i = start_a1, j = start_a2, k = start_a; k < (total_s); k++) {// if reached end of first half array, run through the loop // filling in only from the second half arrayif (i == size_a1) {merged_a[k] = half_a2[j++];continue;}// if reached end of second half array, run through the loop // filling in only from the first half arrayif (j == size_a2) {merged_a[k] = half_a1[i++];continue;}// merged array is filled with the smaller element of the two // arrays, in ordermerged_a[k] = half_a1[i] < half_a2[j] ?half_a1[i++] : half_a2[j++];}}//merge sort data during merging without the additional copying back to array//all data movement is done during the course of the mergesstatic void mergesortNoCopy(int[] a, int[] b, int l, int r) {if (r - l <= M) {insertionsort(a + l, l, r - l);return;}int m = (l + r) / 2;//switch arrays to msort b thus recursively writing results to bmergesortNoCopy(b, a, l, m); //merge sort leftmergesortNoCopy(b, a, m + 1, r); //merge sort right//merge partitions of b into amerge(a, l, b, l, m - l + 1, b, m + 1, r - m); //merge}static void mergesort(int[] a) {int[] aux = Arrays.copyOf(a, a.length);mergesortNoCopy(a, aux, 0, a.length - 1);}

Some other possible improvements:

Stop if already sorted.

Check if the largest item in first half ≤ smallest item in second half.Helps for partially-ordered arrays.

// after split, before mergeif (a[mid] <= a[mid + 1]) return;

EDIT: here is a good document I found on different versions of Mergesort and improvements thereof.