public static void insertionSort(Comparable[] theArray, 
                                 int n) {
// ---------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: theArray is an array of n items.
// Postcondition: theArray is sorted into ascending
// order.
// ---------------------------------------------------
  // unsorted = first index of the unsorted region, 
  // loc = index of insertion in the sorted region, 
  // nextItem = next item in the unsorted region

  // initially, sorted region is theArray[0], 
  //          unsorted region is theArray[1..n-1];
  for (int unsorted = 1; unsorted < n; ++unsorted) {
    // Invariant: theArray[0..unsorted-1] is sorted

    // find the right position (loc) in 
    // theArray[0..unsorted] for theArray[unsorted],  
    // which is the first item in the unsorted  
    // region; shift, if necessary, to make room
    Comparable nextItem = theArray[unsorted];
    int loc = unsorted;

    while ((loc > 0) && 
           (theArray[loc-1].compareTo(nextItem) > 0)) {
      // shift theArray[loc-1] to the right
      theArray[loc--] = theArray[loc-1];
    }  // end while
    // insert nextItem into sorted region
    theArray[loc] = nextItem;
  }  // end for
}  // end insertionSort