MergeSort — optimization of Carrano's code

Carrano's code has the massive problem that every recursive invocation of mergesort generates its own scratch array of the full size of the array being sorted  —  meaning that there is a space complexity of (n log2n) for the algorithm, even though only one scratch array is really needed.

This can be patched easily.

  1. Make the public access to the mergesort method symmetric with public access to other sorting algorithms.
    public void selectsort ( Comparable[] theArray)    // uses theArray.length
    becomes
    public void  mergesort ( Comparable[] theArray)    // uses theArray.length

    Within the public algorithm, (a) allocate the scratch array, (b) pass it to the private method mergesort along with the boundary subscripts.

       public static void mergesort(Comparable[] theArray) {
          Comparable[] tempArray = new Comparable[theArray.length];
    
          // Invoke the private method that does ALL the work
          mergesort (theArray, tempArray, 0, theArray.length-1);
       } // end public mergesort  
  2. The private method mergeSort does the splitting and recursive calls, and then passes the scratch array along to the merge method.
       private static void mergesort(Comparable[] theArray, Comparable[] tempArray,
                                     int first, int last) {
          if (first < last) {
             // sort each half
             int mid = (first + last)/2;                   // index of midpoint
             mergesort(theArray, tempArray, first, mid);   // sort left half theArray[first..mid]
             mergesort(theArray, tempArray, mid+1, last);  // sort right half theArray[mid+1..last]
             merge(theArray, tempArray, first, mid, last); // merge the two halves
          }  // end if
       }  // end private mergesort
  3. The merge method does not allocate its own scratch space; it uses what was provided as a parameter.
    [Note:  somewhat compressed for display purposes through combining postincrementing with subscripting.  The author was a C programmer long before he programmed in Java.]
       private static void merge(Comparable[] theArray, Comparable[] tempArray,
                                 int first, int mid, int last) {
          // initialize the local indexes to indicate the subarrays
          int first1 = first;    // beginning of first subarray
          int last1  = mid;      // end of first subarray
          int first2 = mid + 1;  // beginning of second subarray
          int last2  = last;     // end of second subarray
          // while both subarrays are not empty, copy the
          // smaller item into the temporary array
          int index = first1;    // next available location in
                                 // tempArray
          // Invariant for all loops: tempArray[first1..index-1] is in order
          while ((first1 <= last1) && (first2 <= last2)) {
             if (theArray[first1].compareTo(theArray[first2])<0)
                tempArray[index++] = theArray[first1++];
             else
                tempArray[index++] = theArray[first2++];
          }  // end while
    
          while (first1 <= last1) // finish off the first subarray, if necessary
             tempArray[index++] = theArray[first1++];
    
          while (first2 <= last2) // finish off the second subarray, if necessary
             tempArray[index++] = theArray[first2++];
    
          // copy the result back into the original array
          for (index = first; index <= last; ++index)
              theArray[index] = tempArray[index];
        }  // end merge

This still has the massive overhead of copying each array segment from the scratch array back into the parameter array at every step.

For an iterative implementation that avoids this copying (be moving back and forth between the parameter array and the scratch array)
follow this link.


Java Code Files

MergeDriver.java    Program to exercise the mergesort algorithm.  Nearly identical to the website version.
MergeSort.java       public class MergeSort, with logic embedded to generate a trace of execution
MergeSort.rtf          Word-processor file listing the above programs as two sides of two-column text.

Specimen run from the above program:

Initial state of the array:
  9 15 13 20  5  0  7 10  3  2
Result of merging 0 to 0 with 1 to 1
  9 15
Result of merging 0 to 1 with 2 to 2
  9 13 15
Result of merging 3 to 3 with 4 to 4
           5 20
Result of merging 0 to 2 with 3 to 4
  5  9 13 15 20
Result of merging 5 to 5 with 6 to 6
                 0  7
Result of merging 5 to 6 with 7 to 7
                 0  7 10
Result of merging 8 to 8 with 9 to 9
                          2  3
Result of merging 5 to 7 with 8 to 9
                 0  2  3  7 10
Result of merging 0 to 4 with 5 to 9
  0  2  3  5  7  9 10 13 15 20