/**
 * Sam's version of Insertion sort.
 */

public class InsertionSort
  implements Sorter
{ 
   
  // +------------------+----------------------------------------
  // | Exported Methods |
  // +------------------+

    public Object[] sort(Object[] toSort, GComparator comp){
      for (int i = 1; i < toSort.length; i++) {
        insert(toSort,i,comp);
      }
      return toSort;
    }//sort (Object[])


    /**
     * Fix up the elements at positions 0 ... pos by inserting the
     * element at position pos in the correct space.
     * Pre: Elements at positions 0 ... pos-1 are in correct order.
     */
    private void insert(Object[] toSort, int pos, GComparator comp){
      // Keep swapping to the left until you run out of elements
      // or find one smaller.  
      while (pos > 0 && comp.mayPrecede(toSort[pos],toSort[pos-1])) {
        swap(toSort, pos, pos-1);
        pos = pos-1; 
      } // while
    }//insert(Object[])
   
    /**
     * Swap the values at positions x and y in the array stuff.
     */
    private void swap(Object[] stuff, int x, int y) {
      Object tmp = stuff[x];
      stuff[x] = stuff[y];
      stuff[y] = tmp;
    } // swap(Object, x, y)
} // class InsertionSort