Quicksort partition schemes on duplicate values

Three-way quicksort puts values smaller than the pivot, equal to the pivot, and larger than the pivot into separate regions. The equal region is already finished and needs no recursive sorting. For a student who has learned ordinary quicksort, a list with many repeated values shows why this extra region can change the amount of work substantially.

The comparison must name the two-way scheme. A Lomuto-style partition that moves only values strictly smaller than a final pivot produces an empty smaller side on all-equal input, then recurses on the remaining n - 1 values. That version takes quadratic work on the input. Other two-way schemes, including carefully implemented Hoare partitioning, behave differently on equal values; “two-way quicksort is always quadratic with duplicates” would be too broad.

Maintain four regions during the scan

Use indices lt, i, and gt, starting at zero, zero, and the array length. Before each iteration, [0, lt) contains values smaller than the pivot, [lt, i) contains equal values, [i, gt) is unclassified, and [gt, n) contains larger values.

def partition_three_way(values, pivot):
    lt = i = 0
    gt = len(values)
    while i < gt:
        if values[i] < pivot:
            values[lt], values[i] = values[i], values[lt]
            lt += 1
            i += 1
        elif values[i] > pivot:
            gt -= 1
            values[i], values[gt] = values[gt], values[i]
        else:
            i += 1
    return lt, gt

values = [4, 2, 4, 5, 4, 1]
lo_equal, hi_equal = partition_three_way(values, 4)
assert values == [2, 1, 4, 4, 4, 5]
assert (lo_equal, hi_equal) == (2, 5)

When the current value is smaller, exchange it with the first equal value and advance both left boundaries. If lt == i, that exchange is just a self-swap. When the current value is equal, extend the equal region by advancing i.

When the value is larger, exchange it with the last unclassified slot after decreasing gt. Do not advance i yet: the value brought back from the right has not been classified. Skipping that check is a common bug because it can leave a small value inside the equal region.

View full-size image ↗

For the example, the first four extends the equal region. Two then swaps to the front, and the next four joins the equal region. Five swaps with the last unclassified value, one. Because i stays put, one is examined next and moved into the smaller region. The remaining four completes the scan.

Partitioning is not sorting each region

The smaller region in the result is [2, 1], which is not sorted. The partition’s promise concerns the relation to the pivot, not the internal order of either outside region. A full quicksort recursively sorts [0, lt) and [gt, n) and leaves [lt, gt) alone.

Each iteration reduces gt - i, the number of unclassified values, by one. The loop therefore runs exactly n iterations for this complete-array partition, though an iteration can perform one or two key comparisons. It uses constant auxiliary storage and rearranges the array in place.

The region invariant proves the result when i == gt: the unclassified region is empty, so every value belongs to the correct relation to the pivot. Swaps preserve all input occurrences, including duplicates. No separate counting or copying of the equal values is needed.

On an all-equal array, one partition classifies all values and both recursive outside ranges are empty. This gives linear work for that case. Princeton’s quicksort material and its three-way implementation describe this treatment of duplicate keys.

Pivot choice still affects distinct values

The remaining limitation is pivot choice. If every value is distinct and a deterministic algorithm repeatedly selects the smallest remaining pivot, three-way partitioning creates an equal region of size one and a remaining range of size n - 1. Its total work can still be Θ(n²). Separating equal keys solves duplicate recursion; it does not guarantee balanced partitions for arbitrary inputs.

Randomly selecting pivots or shuffling the input supports expected O(n log n) quicksort analysis under the corresponding randomness model. A carefully chosen deterministic pivot policy or a fallback sorting method gives different guarantees. State which policy is implemented before quoting an average or worst-case bound.

The recursive stack can also become linear in a naive implementation with highly unbalanced partitions. Recursing on the smaller region and processing the larger one in a loop bounds the number of simultaneously active calls by O(log n), even if total comparison work remains quadratic. Time and stack guarantees should be evaluated separately.

Test the regions and the preserved values

A test that compares the partitioned array with a fully sorted array demands more than the function promises. Instead, assert that all values before lt are smaller, all values from lt to gt equal the pivot, and all later values are larger. Also compare value frequencies before and after to catch a lost or duplicated element.

Exercise an empty array, all-equal values, a pivot absent from the array, and alternating small and large values. The standalone partition supports an absent pivot by returning an empty equal region, although a full quicksort normally chooses a pivot from its current range. If records have equal keys, this swapping scheme is not stable; use a stable sorting method when their original relative order is part of the required output.

Bound the stack while keeping the same partition work

A complete implementation can use half-open subranges of one list and recurse only into the smaller outside region. Process the larger region by changing the current loop’s bounds. The partition still examines every value in its current range; this scheduling change limits simultaneously active calls without improving a bad pivot sequence’s comparison count.

The function below returns the maximum number of active sorting calls so the space argument can be checked. Empty and one-element inputs need no sorting call and return zero. The return value is a frame count, not bytes or total recursive calls. The input list is the sorted result.

def quicksort_three_way(values):
    peak = 0

    def sort_range(lo, hi, depth):
        nonlocal peak
        peak = max(peak, depth)
        while hi - lo > 1:
            pivot = values[lo]
            lt = i = lo
            gt = hi
            while i < gt:
                if values[i] < pivot:
                    values[lt], values[i] = values[i], values[lt]
                    lt += 1
                    i += 1
                elif values[i] > pivot:
                    gt -= 1
                    values[i], values[gt] = values[gt], values[i]
                else:
                    i += 1
            if lt - lo < hi - gt:
                if lt - lo > 1:
                    sort_range(lo, lt, depth + 1)
                lo = gt
            else:
                if hi - gt > 1:
                    sort_range(gt, hi, depth + 1)
                hi = lt

    if len(values) > 1:
        sort_range(0, len(values), 1)
    return peak

repeated = [4] * 16
assert quicksort_three_way(repeated) == 1
mixed = [4, 2, 4, 5, 4, 1]
quicksort_three_way(mixed)
assert mixed == [1, 2, 4, 4, 4, 5]
assert quicksort_three_way([]) == 0

Here the pivot belongs to the active range, so the equal region contains at least one value. For a range of size m, the two outside regions therefore contain at most m - 1 values in total. The smaller one has at most floor((m - 1) / 2) values. Each extra recursive frame enters that smaller region, so repeatedly adding frames at least halves the active size. That gives O(log n) peak sorting frames, even though a frame can process many larger ranges through its loop.

View full-size image ↗

The figure’s extreme-pivot sequence is a conditional cost example, not a claim that every sorted input follows that exact trace in this swapping implementation. If each pivot is the smallest remaining distinct value, the ranges shrink from sixteen to fifteen and so on down to two. Partition iterations total 16 + 15 + ... + 2 = 135, yet there is only one active sorting frame: the empty smaller side never receives a call. With sixteen equal values, the first partition performs sixteen iterations and completes the sort in one frame. Identical stack peaks can hide very different work.

No slice is created in the full implementation. Its list rearrangement uses constant working state per frame, but recursion adds O(log n) auxiliary state, so calling the whole sort constant-space would be inaccurate. It remains unstable, assumes coherent comparisons, and uses the first active value as a deterministic pivot. The stack improvement alone supplies no expected-time claim.

Extend the tests with tagged equal-key records if you add a key function, and with short integer arrays enumerated over a small value set. Check sorted output, preserved occurrences and the reported peak separately. For n >= 2, floor(log2(n)) is a safe upper bound for this implementation’s active sorting frames. A test of that bound cannot establish a fast runtime; keep the work counter separate if you instrument the partitions.