Merge method in MergeSort Algorithm .

Posted by Tony on Stack Overflow See other posts from Stack Overflow or by Tony
Published on 2010-03-20T14:37:30Z Indexed on 2010/03/20 14:41 UTC
Read the original article Hit count: 709

Filed under:
|
|

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.

© Stack Overflow or respective owner

Related posts about java

Related posts about algorithm