/**
* 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 QuickSorter extends ASorter{
    public final static QuickSorter Singleton = new QuickSorter ();
    private QuickSorter(){
    }
    /**
    * Splits A[lo:hi] in such a way that A[lo:s-1] <= A[s:hi] with lo < s <= hi.
    * @param A
    * @param lo < hi.
    * @param hi > lo.
    * @return s such that A[lo:s-1] <= A[s:hi], lo < s <= hi.
    */
    public int split(int[] A, int lo, int hi){
        int 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: if lx <= rx, there exists ix in [lo:rx] such that A[ix] <= key.
    // Invariant 4: if lx <= rx, there exists jx in [lx:hi] such that key <= A[jx].
        while (lx <= rx){
            while (key < A[rx]){ // will terminate due to invariant 3.
                rx--;  // Invariant 1 is maintained.
            } // A[rx] <= key <= A[rx+1:hi]; lx <= rx.

            while (A[lx] < key){ // 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]:
                int 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
    */
    public void join(int[] A, int lo, int s, int hi){
     // nothing to do!
    }

    public static void main(String[] args){
        int[] A = {99, -34, 0, 5, -7, 0, 99};
//        int[] A = {99, 99, 99}; // ACID TEST!
        System.out.println ("A =");
        for (int i = 0; i < A.length; i++) {
            System.out.print (A[i] + "  ");
        }
        System.out.println ();
        System.out.println ("Sorting A...");
        QuickSorter.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");
    }
}