§ My preferred version of quicksort

Wikipedia lists the implementation of quicksort as: 
algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i
Here, the indeces [lo..i-1] have values less than the pivot, while [i..j] are great or equal to the pivot.

§ The version I prefer 

// #define SWAP(ix, ix2) { int t = a[ix]; a[ix] = a[ix2]; a[ix2] = t; }
// sorts the interval [l, r]
void qs(int l, int r) {
    if (r - l < 0) return;
    int part = a[r]; // the partition

    // a[getill...n] >= part (getill = greater or equal till)
    // starts at r since we know that a[r] >= (partition=a[r])
    int getill = r;
    // a[l..lttill] < part (lttill = less or equal till.
    // starts at (l-1) since we do not know about any value < partition
    int lttill = l-1;


    // loop until they start probing into the other set
    while(!(lttill+1 >=getill || getill-1 <=lttill)) {
        // if the speculated element is < partition
        if (a[getill-1] < part) {
            // swap the value at getill-1 will the slot at lttill+1
            SWAP(getill-1, lttill+1);
            // increment lttill, since we KNOW that the
            // value at lttill+1 = a[getill-1] is < part
            lttill++;
        } else {
            // all we know is that a[getill-1] < part, so we can engulf
            // the region into
            getill--;
        }
    }
    // the partitions must be next to each other, since we have engulfed everything
    assert(getill - lttill == 1);
    // move the partition value to the center.
    SWAP(getill, r);

    // recurse:solve [l..littil] (leave getill=part alone) solve [getill+1..r]
    qs(l, lttill);
    qs(getill+1, r);
}
This implementation to me makes very clear to me what information is "known":
  • The segments that is strictly less than the partition.
  • The segment that is strictly great or equal the partition.
It also makes clear what is being "probed"/"tentative":
  • anything we are accessing as +-1 is not known yet, we are feeling out the boundaries of our partitions.
The termination condition is clear: when one partition starts reaching into the other partitions resources, its done. Due to using closed intervals everywhere, it's very easy to see precisely what data starts and ends where. What version of quicksort do you prefer? Drop me an email!