Linear-time Partitioning

The real work of quicksort happens during the divide step, which partitions subarray $array[p \cdots r]$ around a pivot drawn from the subarray. Although we can choose any element in the subarray as the pivot, it's easy to implement partitioning if we choose the rightmost element of the subarray, $A[r]$, as the pivot.

Having chosen a pivot, we partition the subarray by going through it, left to right, comparing each element with the pivot. We maintain two indices q and j into the subarray that divide it up into four groups. We use the variable name q because that index will eventually point at our pivot. We use j because it's a common counter variable name, and the variable will be discarded once we're done.

• The elements in $array[p \cdots q-1]$ are "group L," consisting of elements known to be less than or equal to the pivot.

• The elements in $$ ...