Yet Another Code Snippet for Merge Sort (Java)

Conceptually, merge sort works as follows:

1. Divide the unsorted list into two sublists of about half the size
2. Sort each of the two sublists
3. Merge the two sorted sublists back into one sorted list.

The algorithm was invented by John von Neumann in 1945.

The following code shows how to implement merge sort in Java.

/**      * Mergesort algorithm.      * @param a an array of Comparable items.      */     public static void mergeSort( Comparable [ ] a ) {         Comparable [ ] tmpArray = new Comparable[ a.length ];         mergeSort( a, tmpArray, 0, a.length - 1 );     }          /**      * Internal method that makes recursive calls.      * @param a an array of Comparable items.      * @param tmpArray an array to place the merged result.      * @param left the left-most index of the subarray.      * @param right the right-most index of the subarray.      */     private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,             int left, int right ) {         if( left < right ) {             int center = ( left + right ) / 2;             mergeSort( a, tmpArray, left, center );             mergeSort( a, tmpArray, center + 1, right );             merge( a, tmpArray, left, center + 1, right );         }     }          /**      * Internal method that merges two sorted halves of a subarray.      * @param a an array of Comparable items.      * @param tmpArray an array to place the merged result.      * @param leftPos the left-most index of the subarray.      * @param rightPos the index of the start of the second half.      * @param rightEnd the right-most index of the subarray.      */     private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,             int leftPos, int rightPos, int rightEnd ) {         int leftEnd = rightPos - 1;         int tmpPos = leftPos;         int numElements = rightEnd - leftPos + 1;                  // Main loop         while( leftPos <= leftEnd && rightPos <= rightEnd )             if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )                 tmpArray[ tmpPos++ ] = a[ leftPos++ ];             else                 tmpArray[ tmpPos++ ] = a[ rightPos++ ];                  while( leftPos <= leftEnd )    // Copy rest of first half             tmpArray[ tmpPos++ ] = a[ leftPos++ ];                  while( rightPos <= rightEnd )  // Copy rest of right half             tmpArray[ tmpPos++ ] = a[ rightPos++ ];                  // Copy tmpArray back         for( int i = 0; i < numElements; i++, rightEnd-- )             a[ rightEnd ] = tmpArray[ rightEnd ];     }