Carrano's code has the massive problem that __every recursive
invocation__ of mergesort generates its

This can be patched easily.

- 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.lengthWithin 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

- 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

- 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.

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