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 logn 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).
staticvoidmergesort(Comparable[]A,Comparable[]temp,intleft,intright){if(left==right){return;}// List has one recordintmid=(left+right)/2;// Select midpointmergesort(A,temp,left,mid);// Mergesort first halfmergesort(A,temp,mid+1,right);// Mergesort second halffor(inti=left;i<=right;i++){// Copy subarray to temptemp[i]=A[i];}// Do the merge operation back to Ainti1=left;inti2=mid+1;for(intcurr=left;curr<=right;curr++){if(i1==mid+1){// Left sublist exhaustedA[curr]=temp[i2++];}elseif(i2>right){// Right sublist exhaustedA[curr]=temp[i1++];}elseif(temp[i1].compareTo(temp[i2])<=0){// Get smaller valueA[curr]=temp[i1++];}else{A[curr]=temp[i2++];}}}
voidmergesort(Comparable*A[],Comparable*temp[],intleft,intright){if(left==right)return;// List has one recordintmid=(left+right)/2;// Select midpointmergesort(A,temp,left,mid);// Mergesort first halfmergesort(A,temp,(mid+1),right);// Mergesort second halffor(inti=left;i<=right;i++)// Copy subarray to temp*temp[i]=*A[i];// Do the merge operation back to Ainti1=left;inti2=mid+1;for(intcurr=left;curr<=right;curr++){if(i1==mid+1)// Left sublist exhausted*A[curr]=*temp[i2++];elseif(i2>right)// Right sublist exhausted *A[curr]=*temp[i1++];elseif(*temp[i1]<=*temp[i2])// Get smaller value*A[curr]=*temp[i1++];else*A[curr]=*temp[i2++];}}
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.
staticvoidmergesortOpt(Comparable[]A,Comparable[]temp,intleft,intright){inti,j,k,mid=(left+right)/2;// Select the midpointif(left==right){return;}// List has one recordif((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 arrayfor(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--];}}}
voidmergesortOpt(Comparable*A[],Comparable*temp[],intleft,intright){inti,j,k,mid=(left+right)/2;// Select the midpointif(left==right)return;// List has one recordif((mid-left)>=THRESHOLD)mergesortOpt(A,temp,left,mid);elseinssort(A,left,mid);if((right-mid)>THRESHOLD)mergesortOpt(A,temp,mid+1,right);elseinssort(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 arrayfor(i=left,j=right,k=left;k<=right;k++)if(*temp[i]<=*temp[j])*A[k]=*temp[i++];else*A[k]=*temp[j--];}
