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 $array[q \cdots j-1]$ are "group G," consisting of elements known to be greater than the pivot.

• The elements in $array[j \cdots r-1]$ are "group U," consisting of elements whose relationship to the pivot is unknown, because they have not yet been compared.

• Finally, $array[r]$ is "group P," the pivot.

Initially, both q and j equal p. At each step, we compare $A[j]$, the leftmost element in group U, with the pivot. If $A[j]$ is greater than the pivot, then we just increment j, so that the line dividing groups G and U slides over one position to the right: