10.9. Implementing Mergesort¶
10.9.1. Implementing Mergesort¶
Implementing Mergesort presents a number of technical difficulties.
The first decision is how to represent the lists.
Mergesort lends itself well to sorting a singly linked list because
merging does not require random access to the list elements.
Thus, Mergesort is the method of choice when the input is in the form
of a linked list.
Implementing merge
for linked lists is straightforward,
because we need only remove items from the front of the input lists
and append items to the output list.
Breaking the input list into two equal halves presents some
difficulty.
Ideally we would just break the lists into front and back halves.
However, even if we know the length of the list in advance, it would
still be necessary to traverse halfway down the linked list to reach
the beginning of the second half.
A simpler method, which does not rely on knowing the length of the
list in advance, assigns elements of the input list alternating
between the two sublists.
The first element is assigned to the first sublist, the
second element to the second sublist, the third to first sublist, the
fourth to the second sublist, and so on.
This requires one complete pass through the input list to build the
sublists.
When the input to Mergesort is an array, splitting input into two subarrays is easy if we know the array bounds. Merging is also easy if we merge the subarrays into a second array. Note that this approach requires twice the amount of space as any of the sorting methods presented so far, which is a serious disadvantage for Mergesort. It is possible to merge the subarrays without using a second array, but this is extremely difficult to do efficiently and is not really practical. Merging the two subarrays into a second array, while simple to implement, presents another difficulty. The merge process ends with the sorted list in the auxiliary array. Consider how the recursive nature of Mergesort breaks the original array into subarrays. Mergesort is recursively called until subarrays of size 1 have been created, requiring \(\log n\) levels of recursion. These subarrays are merged into subarrays of size 2, which are in turn merged into subarrays of size 4, and so on. We need to avoid having each merge operation require a new array. With some difficulty, an algorithm can be devised that alternates between two arrays. A much simpler approach is to copy the sorted sublists to the auxiliary array first, and then merge them back to the original array.
Here is a complete implementation for mergesort following this
approach.
The input records are in array A
.
Array temp
is used as a place to temporarily copy records during
the merge process.
Parameters left
and right
define the left and right
indices, respectively, for the subarray being sorted.
The initial call to mergesort
would be
mergesort(array, temparray, 0, n-1)
.
static void mergesort(Comparable[] A, Comparable[] temp, int left, int right) {
if (left == right) return; // List has one record
int mid = (left+right)/2; // Select midpoint
mergesort(A, temp, left, mid); // Mergesort first half
mergesort(A, temp, mid+1, right); // Mergesort second half
for (int i=left; i<=right; i++) // Copy subarray to temp
temp[i] = A[i];
// Do the merge operation back to A
int i1 = left;
int i2 = mid + 1;
for (int curr = left; curr <= right; curr++) {
if (i1 == mid+1) // Left sublist exhausted
A[curr] = temp[i2++];
else if (i2 > right) // Right sublist exhausted
A[curr] = temp[i1++];
else if (temp[i1].compareTo(temp[i2]) <= 0) // Get smaller value
A[curr] = temp[i1++];
else
A[curr] = temp[i2++];
}
}
void mergesort(Comparable* A[], Comparable* temp[], int left, int right) {
if (left == right) return; // List has one record
int mid = (left + right)/2; // Select midpoint
mergesort(A, temp, left, mid); // Mergesort first half
mergesort(A, temp, (mid+1), right); // Mergesort second half
for (int i = left; i <= right; i++) // Copy subarray to temp
*temp[i] = *A[i];
// Do the merge operation back to A
int i1 = left;
int i2 = mid + 1;
for (int curr = left; curr <= right; curr++) {
if (i1 == mid+1) // Left sublist exhausted
*A[curr] = *temp[i2++];
else if (i2 > right) // Right sublist exhausted
*A[curr] = *temp[i1++];
else if (*temp[i1] <= *temp[i2]) // Get smaller value
*A[curr] = *temp[i1++];
else
*A[curr] = *temp[i2++];
}
}
Here is a visualization for the merge step.
An optimized Mergesort implementation is shown below.
It reverses the order of the second subarray during the initial copy.
Now the current positions of the two subarrays work inwards from the
ends, allowing the end of each subarray to act as a sentinel for the
other.
Unlike the previous implementation, no test is needed to check for
when one of the two subarrays becomes empty.
This version also has a second optimization:
It uses Insertion Sort to sort small subarrays whenever the size of
the array is smaller than a value defined by THRESHOLD
.
static void mergesortOpt(Comparable[] A, Comparable[] temp, int left, int right) {
int i, j, k, mid = (left+right)/2; // Select the midpoint
if (left == right) return; // List has one record
if ((mid-left) >= THRESHOLD) mergesortOpt(A, temp, left, mid);
else inssort(A, left, mid);
if ((right-mid) > THRESHOLD) mergesortOpt(A, temp, mid+1, right);
else inssort(A, mid+1, right);
// Do the merge operation. First, copy 2 halves to temp.
for (i=left; i<=mid; i++) temp[i] = A[i];
for (j=right; j>mid; j--) temp[i++] = A[j];
// Merge sublists back to array
for (i=left,j=right,k=left; k<=right; k++)
if (temp[i].compareTo(temp[j]) <= 0) A[k] = temp[i++];
else A[k] = temp[j--];
}
void mergesortOpt(Comparable* A[], Comparable* temp[], int left, int right) {
int i, j, k, mid = (left+right)/2;// Select the midpoint
if (left == right) return; // List has one record
if ((mid-left) >= THRESHOLD) mergesortOpt(A, temp, left, mid);
else inssort(A, left, mid);
if ((right-mid) > THRESHOLD) mergesortOpt(A, temp, mid+1, right);
else inssort(A, mid+1, right);
// Do the merge operation. First, copy 2 halves to temp.
for (i=left; i<=mid; i++) *temp[i] = *A[i];
for (j=right; j>mid; j--) *temp[i++] = *A[j];
// Merge sublists back to array
for (i=left,j=right,k=left; k<=right; k++)
if (*temp[i] <= *temp[j]) *A[k] = *temp[i++];
else *A[k] = *temp[j--];
}
Here is a visualization for the optimized merge step.