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

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)

## 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```