package username.sorting;

import java.util.Comparator;
import java.util.Vector;

/**
 * A sorter that sorts using inserstion sort.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of May 2005
 */
public class InsertionSorter<T>
  implements OutOfPlaceVectorSorter<T>
{
  public Vector<T> sort(Vector<T> vec, Comparator<T> c)
  {
    int len = vec.size();
    Vector<T> sorted = new Vector<T>(len);
    for (int i = 0; i < len; i++) {
      insert(sorted, i-1, vec.get(i), c);
    } // for
    return sorted;
  } // sort(Vector<T>, Comparator<T>)

  /**
   * Insert a value into a sorted vector, with the knowledge
   * that it belongs in postion 0..pos (inclusive).
   */
  void insert(Vector<T> sorted, int pos, T val, Comparator<T> c)
  {
    // Special case: Reached the beginning of the Vector
    if (pos < 0) {
      sorted.add(0, val);
    }
    // Base case: val is greater than or equal to the value
    // at the specified position.  Insert it there
    else if (c.compare(sorted.get(pos), val) < 0) {
      sorted.add(pos+1,val);
    }
    // Otherwise, search backwards
    else {
      insert(sorted, pos-1, val, c);
    } // insert()
  } // insert()
} // class InsertionSorter