private static int partition(Comparable[] theArray, 
                             int first, int last) {
// ---------------------------------------------------------
// Partitions an array for quicksort.
// Precondition: theArray[first..last] is an array; 
// first <= last.
// Postcondition: Returns the index of the pivot element of
// theArray[first..last]. Upon completion of the method, 
// this will be the index value lastS1 such that
//    S1 = theArray[first..lastS1-1] <  pivot
//         theArray[lastS1]          == pivot
//    S2 = theArray[lastS1+1..last]  >= pivot
// Calls: choosePivot.
// ---------------------------------------------------------
  // tempItem is used to swap elements in the array
  Comparable tempItem; 
  // place pivot in theArray[first]             
  choosePivot(theArray, first, last);      
  Comparable pivot = theArray[first];   // reference pivot

  // initially, everything but pivot is in unknown
  int lastS1 = first;          // index of last item in S1

  // move one item at a time until unknown region is empty

  for (int firstUnknown = first + 1; firstUnknown <= last; 
                                    ++firstUnknown) {
    // Invariant: theArray[first+1..lastS1] < pivot
    //            theArray[lastS1+1..firstUnknown-1] >= pivot

    // move item from unknown to proper region
    if (theArray[firstUnknown].compareTo(pivot) < 0) {
      // item from unknown belongs in S1
      ++lastS1;
      tempItem = theArray[firstUnknown];
      theArray[firstUnknown] = theArray[lastS1];
      theArray[lastS1] = tempItem;
    }  // end if
  // else item from unknown belongs in S2
  }  // end for

  // place pivot in proper position and mark its location
  tempItem = theArray[first];
  theArray[first] = theArray[lastS1];
  theArray[lastS1] = tempItem;
  return lastS1;
}  // end partition