/**
* 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 CInsertionSorter extends ACompareSorter {
    public static final CInsertionSorter Singleton = new CInsertionSorter();
    private CInsertionSorter() {
    }

    /**
    * 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.
     */
    protected int split(IOrdered[] A, int lo, int hi) {
        return hi;
    }

    /**
    * Inserts A[s] into the array A[lo:s-1], shifting elements of A to the right if necessary.
     * @param A  A[lo:s-1], A[s:hi] are sorted
     * @param lo
     * @param s == hi.
     * @param hi
     */
    protected void join(IOrdered[] A, int lo, int s, int hi) {
        int j = hi; // remember s == hi.
        IOrdered 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 && key.compare (A[j-1]) == IOrdered.LESS) {
             A[j] = A[j-1];
             j = j - 1;     // invariant is maintained.
        }   // On loop exit: j = lo or A[j-1] <= key. Also invariant is still true.
        A[j] = key;
    }
}