Part I · Quicksort · week 3

3-way quicksort

Partition into less-than, equal-to and greater-than. Arrays with few distinct keys drop from n log n to linear — and duplicates are everywhere in real data.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

distinct keys	linear when few
entropy-optimal	yes
in place	yes
extra cost	more exchanges

Reference: Sedgewick & Wayne, §2.3; Dijkstra.

3-way quicksort in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def sort3(a, lo, hi):
    # INVARIANT:  a[lo..lt-1] < v  =  a[lt..i-1] == v  ?  a[i..gt]  >  a[gt+1..hi]
    if hi <= lo:
        return
    lt, i, gt = lo, lo + 1, hi
    v = a[lo]
    while i <= gt:
        if a[i] < v:
            a[lt], a[i] = a[i], a[lt]     # small: send it left
            lt += 1
            i += 1
        elif a[i] > v:
            a[i], a[gt] = a[gt], a[i]     # large: send it right
            gt -= 1                       # i does NOT advance
        else:
            i += 1                        # equal: it is already home
    sort3(a, lo, lt - 1)                  # only the < and > parts remain
    sort3(a, gt + 1, hi)

Why it works

Three regions, one pass

The invariant names four regions: keys smaller than v, keys equal to v, the unexamined middle, and keys larger than v. Each iteration shrinks the unexamined part by one and keeps all four claims true. When it vanishes, every key equal to the pivot is in its final position — not just one.

Why i does not advance on a large key

The key swapped in from gt has never been examined, so it must be tested next. Advancing i there is the standard bug: it steps over an unknown key and the invariant silently breaks. Only the < and = branches advance i.

The payoff

Ordinary quicksort re-partitions blocks of equal keys again and again. 3-way removes them from the problem in a single pass, so an array with a constant number of distinct values sorts in linear time. Sedgewick and Bentley proved the sort is entropy-optimal: its compares match the information-theoretic lower bound for the input's distribution of duplicate keys.

Real-world context

This is not an exotic case. Sorting records by a low-cardinality field — country, status flag, day of week, DNA base — is the norm, and a widely-used C qsort was once quadratic on such input. Java's Arrays.sort for primitives uses a dual-pivot quicksort partly for the same reason.

What to try in the animation

The payoff shows with duplicates. Compare all equal here (one pass, done) with the same input in ordinary quicksort.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

random — 7 10 5 3 8 4 2 9 6 1
MERGESORTEXAMPLE — M E R G E S O R T E X A M P L E
already sorted — 1 2 3 4 5 6 7 8 9 10
reverse sorted — 10 9 8 7 6 5 4 3 2 1
all equal — 5 5 5 5 5 5 5 5
few distinct — 2 1 3 1 2 3 1 2 3 1

Open 3-way quicksort in the player →

The rest of Quicksort

Quicksort Put one key where it belongs and everything smaller to its left.
Quickselect Partition, then recur on the one side that can contain the answer.