/**
* Sorts by first splitting the array into two subarrays: one is less or equal to the
* first element of the original array, the other is greater or equal to the same
* first element. Then recursively sorts the subarrays to make the original array sorted.
* This algorithm is due to Tony Hoare. In Merritt's sorting taxonomy, this algorithm
* belongs to the family of sorting where the splitting is hard and the joining is easy.
* @author Dung X. Nguyen - Copyright 1999 - All rights reserved.
* @since 11/28/99
*/
public class CQuickSorter extends ACompareSorter {
    public static final CQuickSorter Singleton = new CQuickSorter();
    private CQuickSorter() {
    }
    /**
    * Splits A[lo:hi] in such a way that A[lo:s-1] <= A[s:hi] for some s.
     * @param A
     * @param lo < hi.
     * @param hi > lo.
     * @return s such that A[lo:s-1] <= A[s:hi]
     */
    protected int split(IOrdered[] A, int lo, int hi) {
        IOrdered key = A[lo];
        int lx = lo; // left index.
        int rx = hi; // right index.
        // Invariant 1: key <= A[rx+1:hi].
        // Invariant 2: A[lo:lx-1] <= key.
        // Invariant 3: there exists ix in [lo:rx] such that A[ix] <= key.
        // Invariant 4: there exists jx in [lx:hi] such that key <= A[jx].
        while (lx <= rx) {
            while (key.compare (A[rx]) == IOrdered.LESS) { // will terminate due to invariant 3.
                rx--;  // Invariant 1 is maintained.
            } // A[rx] <= key <= A[rx+1:hi]; also  invariant 0, lx <= rx.

            while (A[lx].compare (key) == IOrdered.LESS) { // will terminate due to invariant 4.
                lx++;  // Invariant 2 is maintained.
            } // A[lo:lx-1] <= key <= A[lx]

         if (lx <= rx)
         {
            // swap A[lx] with A[rx]:
            IOrdered temp = A[lx];
            A[lx] = A[rx]; // invariant 3 is maintained.
            A[rx] = temp;  // invariant 4 is maintained.
            rx--;  // invariant 1 is maintained.
            lx++;  // invariant 2 is maintained.
         }
        } // rx < lx, A[lo:lx-1] <= key <= A[rx+1:hi], and key = A[lx].
                return lx;
    }

    /**
     * @param A  A[lo:s-1] and A[s:hi] are sorted, and A[lo:s-1] <= A[s:hi].
     * @param lo
     * @param s in [lo:hi].
     * @param hi
     */
    protected void join(IOrdered[] A, int lo, int s, int hi) {
    }
}