private static void merge(Comparable[] theArray, 
                          int first, int mid, int last) {
// ---------------------------------------------------------
// Merges two sorted array segments theArray[first..mid] and 
// theArray[mid+1..last] into one sorted array.
// Precondition: first <= mid <= last. The subarrays 
// theArray[first..mid] and theArray[mid+1..last] are 
// each sorted in increasing order.
// Postcondition: theArray[first..last] is sorted.
// Implementation note: This method merges the two
// subarrays into a temporary array and copies the result
// into the original array anArray.
// ---------------------------------------------------------
  int maxSize = theArray.length;
  // temporary array
  Comparable[] tempArray = new Comparable[maxSize]; 

  // 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
  while ((first1 <= last1) && (first2 <= last2)) {
    // Invariant: tempArray[first1..index-1] is in order
    if (theArray[first1].compareTo(theArray[first2])<0) {
      tempArray[index] = theArray[first1];
      first1++;
    }
    else {
      tempArray[index] = theArray[first2];
      first2++;
    }  // end if
    index++;
  }  // end while

  // finish off the nonempty subarray

  // finish off the first subarray, if necessary
  while (first1 <= last1) {
    // Invariant: tempArray[first1..index-1] is in order
    tempArray[index] = theArray[first1];
    first1++;
    index++;
  }  // end while

  // finish off the second subarray, if necessary
  while (first2 <= last2) {
    // Invariant: tempArray[first1..index-1] is in order
    tempArray[index] = theArray[first2];
    first2++;
    index++;
  }  // end while

  // copy the result back into the original array
  for (index = first; index <= last; ++index) {
    theArray[index] = tempArray[index];
  }  // end for
}  // end merge