Merge method in MergeSort Algorithm .
- by Tony
I've seen many mergeSort implementations .Here is the version in Data Structures and Algorithms in Java (2nd Edition) by Robert Lafore :
private void recMergeSort(long[] workSpace, int lowerBound,int upperBound)
{
if(lowerBound == upperBound) // if range is 1,
return; // no use sorting
else
{ // find midpoint
int mid = (lowerBound+upperBound) / 2;
// sort low half
recMergeSort(workSpace, lowerBound, mid);
// sort high half
recMergeSort(workSpace, mid+1, upperBound);
// merge them
merge(workSpace, lowerBound, mid+1, upperBound);
} // end else
} // end recMergeSort()
private void merge(long[] workSpace, int lowPtr,
int highPtr, int upperBound)
{
int j = 0; // workspace index
int lowerBound = lowPtr;
int mid = highPtr-1;
int n = upperBound-lowerBound+1; // # of items
while(lowPtr <= mid && highPtr <= upperBound)
if( theArray[lowPtr] < theArray[highPtr] )
workSpace[j++] = theArray[lowPtr++];
else
workSpace[j++] = theArray[highPtr++];
while(lowPtr <= mid)
workSpace[j++] = theArray[lowPtr++];
while(highPtr <= upperBound)
workSpace[j++] = theArray[highPtr++];
for(j=0; j<n; j++)
theArray[lowerBound+j] = workSpace[j];
} // end merge()
One interesting thing about merge method is that , almost all the implementations didn't pass the lowerBound parameter to merge method . lowerBound is calculated in the merge . This is strange ,
since lowerPtr = mid + 1 ; lowerBound = lowerPtr -1 ; that means lowerBound = mid ;
Why the author didn't pass mid to merge like merge(workSpace, lowerBound,mid, mid+1, upperBound);
?
I think there must be a reason , otherwise I can't understand why an algorithm older than half a center ,and have all coincident in the such little detail.
