/* File: InsertionSort.java - March 2013 */
package l09;

/**
 * Insertion sort (maintain sorted prefix, insert each additional element)
 * 
 * In this standard version the "find position" and "insert" parts are
 * merged by scanning from the position of the element to be inserted
 * rightwards, moving larger elements forwards as necessary. 
 *
 * @author Michael Albert
 *
 */

public class InsertionSort implements IntSorter {


   public void sort(int[] a) {
      for(int i = 0; i < a.length; i++) {
         findAndInsert(a, i, a[i]);
      }
   }

   public String getName() {
      return "Insertion sort";
   }

   private void findAndInsert(int[] a, int index, int value) {
      index--;
      while (index >= 0 && a[index] > value) {
         a[index+1] = a[index];
         index--;
      }
      a[index+1] = value;
   }

}