CQuickSorter.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 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) {
}
}

```
 CQuickSorter.java Created with JBuilder