package Sorter;

/**
 * A concrete sorter that uses the Insertion Sort technique.
 */
public class InsertionSorter extends ASorter
{

	/**
	 * The constructor for this class.
	 * @param iCompareOp The comparison strategy to use in the sorting.
	 */
	public InsertionSorter(AOrder iCompareOp)
	{
		super(iCompareOp);
	}
	/**
	 * Splits A[lo:hi] into A[lo:s-1] and A[s:hi] where s is the returned value of this function.
	 * This simply splits off the element at index hi.
	 * @param A the array A[lo:hi] to be sorted.
	 * @param lo the low index of A.
	 * @param hi the high index of A.
	 * @return hi always.
	 */
	protected int split(Object[] A, int lo, int hi)
	{
		return (hi);
	}

	/**
	 * Joins sorted A[lo:s-1] and sorted A[s:hi] into A[lo:hi].   (s = hi)
	 * The method performs an in-order insertion of A[hi] into the A[lo, hi-1]
	 * @param A A[lo:s-1] and A[s:hi] are sorted.
	 * @param lo the low index of A.
	 * @param s
	 * @param hi the high index of A.
	 */
	protected void join(Object[] A, int lo, int s, int hi)
	{
            int j = hi; // remember s == hi.
            Object key = A[hi];
            // Invariant: A[lo:j-1] and A[j+1:hi] are sorted and key < all elements of A[j+1:hi].
            // Shifts elements of A[lo:j-1] that are greater than key to the "right" to make room for key.
            while (lo < j && aOrder.lt(key, A[j-1]))
            {
               A[j] = A[j-1];
      //         A[j-1] = key;   // This line here just for prettier graphics.
               j = j - 1;     // invariant is maintained.
            }   // On loop exit: j = lo or A[j-1] <= key. Also invariant is still true.
            A[j] = key;   // Normally need this line for actual insert, redundant with pretty graphics line
	}
}