The idea: three parts in one pass
Ordinary quicksort splits a range into two parts: values on one side of the pivot and values on the other. Copies of the pivot land on one side and get sorted again and again. A three-way partition splits the range into three parts: less than the pivot, equal to it, and greater than it. The equal part is already in its final slots, so the recursion only goes into the two other parts. Edsger Dijkstra called this the Dutch national flag problem: sort red, white and blue balls in one pass.
The pass: lt, i and gt
The page takes the pivot value v from the middle slot. Then lt and i start at lo and gt starts at hi. Each step compares a[i] with v once:
- a[i] < v: swap it with a[lt], the first equal value, then lt++ and i++. The blue part grows.
- a[i] > v: swap it with a[gt], then gt−−. The purple part grows. i stays, because the value that came from gt has not been looked at yet.
- a[i] = v: nothing moves, i++. The orange part grows.
The pass stops when i > gt: every value has been compared exactly once. Then the sort calls itself on a[lo..lt − 1] and a[gt + 1..hi] (Demo: four distinct keys, one partition).
One pass sorts three keys
If the array holds only three keys and the pivot is the middle one, a single pass sorts it: everything less is the smallest key, everything greater is the largest. On the demo array of twelve values with keys 1, 2 and 3, the pass makes 12 comparisons and 3 swaps, and both sides end up holding one key each. That is exactly Dijkstra's flag problem (Demo: keys 1, 2, 3, one pass sorts it).
Why duplicates no longer hurt
Each partition fixes every copy of its pivot, so with k distinct keys there are at most k partitions. With all keys equal, one pass of n comparisons and no swaps is the whole sort (Demo: all equal, done after one pass). Lomuto's two-way partition, shown on the counters for the same input, sends every copy of the pivot to one side and peels off one slot per call.
| Input | Three-way: comparisons | Three-way: levels | Two-way Lomuto: comparisons | Two-way Lomuto: levels |
|---|---|---|---|---|
| 12 values, 4 distinct keys (demo) | 21 | 2 | 27 | 4 |
| 12 equal keys (demo) | 12 | 1 | 66 | 11 |
| 1000 values, 3 distinct keys | 2,033 | 3 | 167,524 | 355 |
| 1000 values, 10 distinct keys | 3,799 | 6 | 54,415 | 113 |
| 1000 equal keys | 1,000 | 1 | 499,500 | 999 |
| 1000 different values | 11,403 | 21 | 10,519 | 22 |
Data with few distinct keys is common: status codes, ages, country codes, booleans. Hoare's two-way scheme also avoids the quadratic case by stopping on equal keys (see Lomuto vs Hoare Partition), but it still compares and swaps the copies of the pivot at every level. Three-way partitioning is entropy-optimal: its cost falls toward n as the number of distinct keys drops.
The price on distinct keys
With no duplicates the equal part is just the pivot, and the sort behaves like ordinary quicksort. It does a little more work: each step is a three-way compare (two tests with < in most languages), it compares the pivot with itself, and values from the gt end can be swapped more than once. On the demo array of twelve different values it makes 35 comparisons and 15 swaps against Lomuto's 30 and 21 (Demo: all different, full sort). Bentley and McIlroy's variant keeps the equal keys at both ends during the pass and swaps them into the middle at the end, which removes most of that extra cost.
Where it is used
Java's Arrays.sort for primitive arrays uses a dual-pivot quicksort that also groups keys equal to its pivots. Go's and Rust's pattern-defeating quicksort (pdqsort) switches to a partition that gathers equal keys when it sees the same pivot twice. The same three-way split also keeps Quickselect fast on inputs with many repeats. See also Quick Sort vs Merge Sort and Comparison Sorting.
What the page leaves out
Other pivot rules (random, median of three), Bentley–McIlroy's fast three-way partition, dual-pivot quicksort, switching to insertion sort on small ranges, and the proof that three-way quicksort is optimal for inputs with many duplicates.
See where this page fits on the Sorting mind map.