QuickSorter.java Created with JBuilder
```/**
* 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.
* @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");
}
}

```
 QuickSorter.java Created with JBuilder