/**
* Inserts A[s] into A[lo:s-1], assuming A[lo:s-1] is sorted.
* Correponds to splitting the array at the high index, sort the two parts, and join
* the sorted part.  The splitting is easy.  It's the join that requires some work.
* As such, insertion sort is in the same family as merge sort.
* @author Dung X. Nguyen - Copyright 1999 - all rights reserved.
* @since 11/28/99
*/
public class InsertionSorter extends ASorter
{
	public final static InsertionSorter Singleton = new InsertionSorter();

	private InsertionSorter()
	{
	}
	/**
    * Splits the array at the end (i.e. high index).
	 * @param A array of integers.
	 * @param lo low index of A, < hi.
	 * @param hi high index of A, > lo.
	 * @return hi.
	 */
	public int split(int[] A, int lo, int hi)
	{
		return hi;
	}

	/**
    * Inserts A[s] into the array A[lo:s-1], shifting its elements to the right by one if necessary.
	 * @param A  A[lo:s-1], A[s:hi] are sorted
	 * @param lo 
	 * @param s == hi.
	 * @param hi 
	 */
	public void join(int[] A, int lo, int s, int hi)
	{
      int j = hi; // remember s == hi!
      int key = A[hi];
      // Invariant: A[lo:j-1] and A[j:hi] are sorted and
      //            key <= all elements of A[j:hi] and
      //            A[lo:j-1] <= A[j+1:hi]
      while (lo < j && key < A[j-1])
      // Shifts elements of A[lo:j-1] that are greater than key to the "right" to make room for key.
      {
         A[j] = A[j-1]; 
         j = j - 1;     // invariant is maintained.
      }   // On loop exit: j = lo or A[j-1] <= key. Also invariant still holds.
      A[j] = key;
      // A[lo:hi] is sorted because:
      // A[lo:j-1] is sorted, A[j-1] <= key == A[j] <= A[j+1:hi], and A[j+1:hi] is sorted.

      /*
      // Equivalent "for" loop:
      int j;
      int key = A[hi];
      for (j = hi; lo < j && key < A[j-1]; j--)
      {
         A[j] = A[j-1];
      }
      A[j] = key;
      */
	}

   /**
   * A simple test case for InsertionSorter.
   */
	public static void main(String[] args)
	{
      int[] A = {99, -34, 0, 5, -7, 0};
      System.out.println ("A =");

      for (int i = 0; i < A.length; i++)
      {
         System.out.print (A[i] + "  ");
      }  // Should write this loop as a print utility for arrays.

      System.out.println ();
      System.out.println ("Insertion sorting A...");
      InsertionSorter.Singleton.sort (A, 0, A.length - 1);
      System.out.println ("Sorted A =");

      for (int i = 0; i < A.length; i++)
      {
         System.out.print (A[i] + "  ");
      }
      
      System.out.println ("\nDone");
	}
}