Quicksort Partition Schemes and the Duplicate-Key Quadratic

Quicksort’s recursion is trivial; the partition is the algorithm. Swap count, branch predictability, behaviour on equal keys, and worst-case depth all follow from how the partition loop moves elements and where it places the pivot. Two partition schemes dominate implementations, and the difference between them is not stylistic.

The two-loop invariant

Hoare’s original scheme scans from both ends. A left index advances while elements are smaller than the pivot; a right index retreats while elements are larger; when both stop, the two elements are swapped and scanning resumes. The invariant is that everything left of the left index is $\le$ the pivot and everything right of the right index is $\ge$ it.

/* Hoare partition on a[lo..hi]; returns a split index p with lo <= p < hi */
static size_t hoare_partition(int *a, size_t lo, size_t hi)
{
    int pivot = a[lo + (hi - lo) / 2];
    ptrdiff_t i = (ptrdiff_t)lo - 1, j = (ptrdiff_t)hi + 1;
    for (;;) {
        do { i++; } while (a[i] < pivot);
        do { j--; } while (a[j] > pivot);
        if (i >= j) return (size_t)j;
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

The scheme compares against the pivot value, which was copied out beforehand, so no element is special and the pivot needs no final placement. Both indices stop on elements equal to the pivot, and the swap exchanges them. The result is two parts, each of which may contain keys equal to the pivot, and the returned index j satisfies lo <= j < hi, which is what makes the recursion terminate.

Lomuto’s scheme is simpler to state and worse in practice. It keeps a boundary index and advances a scanning index; every element of the range before the pivot that is smaller than the pivot is swapped to the boundary, and the pivot is swapped into the boundary at the end. It performs one swap per element smaller than the pivot plus a final pivot swap, whereas Hoare performs one swap per pair of misplaced elements. On random input Lomuto’s swap count is therefore higher by roughly a factor of two, because a single pair swap fixes two misplaced elements at once.

The other difference is branch behaviour. Lomuto’s inner test is a single comparison whose outcome is usually false, and the swap is conditional on it; the branch is taken for a fraction of elements equal to the proportion below the pivot. Hoare’s inner loops are two tight do/while scans, each of which is a compare-and-increment with no data movement in the common case. The scans are also two independent streams, which the hardware can overlap; Lomuto’s single forward pass with conditional swaps is more serial.

Why equal keys break the two-way schemes

Take an array of $n$ identical keys. Under Lomuto with a strict < test, no element is ever smaller than the pivot, so the boundary never advances, the pivot lands at the left end, and the recursion splits into a part of size 0 and a part of size $n-1$. That is the worst possible split at every level: $\Theta(n^2)$ comparisons and $\Theta(n)$ stack depth.

Under Hoare with the strict < and > tests above, both scans stop on the first element they meet, the swap exchanges two equal elements, and the scans continue. The partition splits the array roughly in half and the cost is $\Theta(n \log n)$. The difference is that Hoare’s scans stop on equality rather than skipping past it, which spreads equal keys across both sides.

This is not a corner case to be waved away. Keys drawn from a small domain, such as status codes, byte values, ages, bucket identifiers, or a sort key that is a prefix of a longer identifier, produce large groups of equals routinely. A two-way partition that skips equals is quadratic on exactly those inputs.

Three-way partitioning as the general fix

The general answer is to partition into three regions in one pass: keys less than the pivot, keys equal to it, and keys greater. The equal region is then excluded from both recursive calls, so a run of $n$ identical keys is finished after one partition.

The Dutch-national-flag loop does this with three indices: lt (boundary of the less region), i (the scan), and gt (boundary of the greater region, scanning downward).

/* three-way partition a[lo..hi]; returns lt and gt via pointers */
static void partition3(int *a, size_t lo, size_t hi, size_t *lt_out, size_t *gt_out)
{
    int pivot = a[lo];
    size_t lt = lo, i = lo + 1, gt = hi;
    while (i <= gt) {
        if (a[i] < pivot)      { int t = a[lt]; a[lt] = a[i]; a[i] = t; lt++; i++; }
        else if (a[i] > pivot) { int t = a[i]; a[i] = a[gt]; a[gt] = t; gt--; }
        else                   { i++; }
    }
    *lt_out = lt;
    *gt_out = gt;
}

The invariant: a[lo..lt) is less, a[lt..i) is equal, a(gt..hi] is greater, and a[i..gt] is unexamined. Each element is examined once, so the pass is linear, and every element that is swapped into the scan position is unexamined, so nothing is skipped. In the return values, gt_out is the last position of the equal region, so the equal region is [lt, gt] and recursion covers only [lo, lt) and (gt, hi].

The cost is more branches per element: three cases instead of one comparison. On inputs with few duplicates the extra branching costs more than the equal-key handling saves. This is why implementations do not use three-way partitioning unconditionally; they either estimate duplicate density from a sample or apply it only in a fallback path. A common compromise partitions with a two-way scheme but stops both scans on keys equal to the pivot, which spreads duplicates across the two sides and keeps the split balanced without paying the third branch.

Pivot selection and the depth budget

The partition scheme fixes the cost of one level; pivot selection fixes the shape of the recursion. Choosing the first or last element gives $\Theta(n^2)$ on already-sorted input, which is common enough to matter. Median-of-three (first, middle, last) removes the sorted and reverse-sorted cases and costs at most three comparisons. Median-of-medians gives a guaranteed linear-time pivot at a large constant and no library sort uses it as its primary pivot rule.

A method with lower variance samples a small number of elements, sorts the sample, and uses its median, which reduces the variance of the split ratio at modest cost. Whatever the method, an adversary who can predict the pivot can force a bad split, so implementations that must resist adversarial input combine randomisation with a hard cap on recursion depth. That cap is the subject of introsort and depth-limited hybrids.

The recursion that is not recursion

Quicksort’s second recursive call is in tail position: after partitioning, the call on the larger side can be replaced by a loop, and only the smaller side recurses. Since the smaller side is at most half the range, the stack depth is bounded by $\log_2 n$ regardless of how bad the splits are. The total work is unchanged; only the stack usage improves, from potentially $\Theta(n)$ to $\Theta(\log n)$.

This is a strictly better formulation of the same algorithm and costs nothing to implement. It is also independent of pivot quality: even a pivot rule that always produces a 1-to-$n-1$ split keeps the stack bounded, though the time remains quadratic.

Small-array behaviour and the base case

Below roughly 10 to 20 elements, the recursion overhead and the poor branch prediction of partitioning outweigh the asymptotic advantage, and insertion sort finishes faster. Libraries typically switch at a threshold in that range, chosen by measurement on the target architecture rather than derived.

An alternative used in some implementations avoids the threshold entirely: leave small ranges unsorted during recursion, then run one insertion-sort pass over the whole array at the end. The pass is cheap when the array is nearly sorted, and partitioning leaves it so, because every element sits within a bounded distance of its final position once all but the small unsorted ranges have been placed. In terms of the inversion count the pass costs $n$ plus whatever inversions remain, and the unsorted ranges are the only source of them. The single final pass has better locality than many small scattered calls.

What partitioning cannot fix

Quicksort moves each element at most once per level, but the swaps are scattered: the left scan reads forward and the right scan reads backward, and each swap writes to two distant locations. On arrays larger than cache this costs up to two cache misses per swap, and the total memory traffic is again $\Theta(n \log n)$ elements, with far less locality than merge sort’s sequential streaming. Partitioning cannot be made sequential without giving up the in-place property, which is why the two algorithms remain complementary rather than one replacing the other.

Duplicates are handled by the partition scheme, not by the pivot; no pivot choice rescues a two-way partition that skips equals. And the quadratic worst case is handled by the depth cap, not by better pivots; a cap converts the bad case into a guaranteed $O(n \log n)$ by switching algorithms, which means the result is no longer pure quicksort.