The idea: the partition step decides how fast quick sort is
Quick sort picks a pivot, then partitions the range: small values go to the left, large values to the right. Then it sorts each side. All the real work happens in the partition, and there are two classic ways to write it. Lomuto's scheme uses one scan from the left. Hoare's scheme, the original from 1961, uses two scans that move towards each other. The page runs both on the same array with the same pivot value, the middle element, and counts comparisons, swaps and how deep the recursion goes.
Lomuto: one scan
The page first swaps the middle element to the end, a[hi], so it can stay out of the way. Then j walks from lo to hi − 1. The values before i are ≤ pivot (blue), the values from i to j − 1 are > pivot (purple).
- If a[j] ≤ pivot: swap a[i] and a[j], then i++. This swap happens even when the value is already in place, so on sorted input most swaps are a value swapped with itself.
- Otherwise the value stays where it is and the purple part grows by one.
At the end, the pivot is swapped into a[i]. That is its final slot (green), so the two recursive calls skip it. The code is short and easy to get right, which is why textbooks like it (Demo: random array, one partition).
Hoare: two scans
i moves right past values < pivot and stops. j moves left past values > pivot and stops. Both stopped values are on the wrong side, so they are swapped and the scans go on. When i ≥ j, the range is split after a[j]: everything in a[lo..j] is ≤ pivot and everything in a[j + 1..hi] is ≥ pivot (the dark bar on the canvas).
Two details differ from Lomuto. Only misplaced pairs are swapped, so on sorted input Hoare makes no swaps at all (Demo: already sorted, one partition). And the pivot is not put in a final slot: it is just one value on one side, so the next calls are sort(lo, j) and sort(j + 1, hi), with no slot left out.
What the counters show
| Input (n = 10) | One partition: swaps | Full sort: comparisons | Full sort: swaps | Full sort: levels |
|---|---|---|---|---|
| Random (demo array) | Lomuto 7, Hoare 2 | Lomuto 19, Hoare 53 | Lomuto 19, Hoare 10 | Lomuto 3, Hoare 5 |
| Already sorted | Lomuto 6, Hoare 0 | Lomuto 19, Hoare 43 | Lomuto 19, Hoare 0 | Lomuto 3, Hoare 4 |
| Three keys | Lomuto 8, Hoare 3 | Lomuto 25, Hoare 51 | Lomuto 35, Hoare 10 | Lomuto 5, Hoare 5 |
| All equal | Lomuto 11, Hoare 5 | Lomuto 45, Hoare 48 | Lomuto 63, Hoare 15 | Lomuto 9, Hoare 4 |
Hoare swaps about three times less: averaged over many random arrays, one partition of 10 values costs Lomuto 6.5 swaps and Hoare 2.1. Hoare pays with some extra comparisons. Its two scans overlap by a slot or two where they cross, and because it never fixes the pivot it partitions more, smaller ranges. On 1000 random values Lomuto makes about 10,900 comparisons and 6,900 swaps; Hoare makes about 14,500 comparisons and 2,300 swaps. A swap writes two slots and a comparison only reads, so Hoare is usually the faster of the two.
Equal keys: where Lomuto breaks down
Lomuto's test is a[j] ≤ pivot. When every key equals the pivot, every value goes left, the pivot lands at the end, and the split is n − 1 | 0. Each call removes one slot, so the recursion is n − 1 levels deep and the sort costs n(n − 1)/2 comparisons: quick sort's O(n²) worst case, caused by the partition and not by a bad pivot.
Hoare's scans both stop on a value equal to the pivot. That looks wasteful, since equal values get swapped, but it makes the scans meet in the middle, so the split is even and the depth stays about log₂ n (Demo: all equal, full sort). At 10 keys the totals are still close; at 1000 equal keys Lomuto needs 499,500 comparisons and 999 levels, Hoare about 11,900 comparisons and 10 levels. Inputs with a few distinct keys, such as ages or status codes, behave the same way (Demo: many duplicates, full sort).
Which one to use
| Lomuto | Hoare | |
|---|---|---|
| Scans | one, left to right | two, towards each other |
| Swaps | one per value ≤ pivot | one per misplaced pair, about 3 times fewer |
| Pivot after the partition | in its final slot | somewhere in one side |
| Many equal keys | lopsided splits, O(n²) | even splits |
| Easy to get right | yes | tricky: the pivot choice and the ≥/≤ stops must match, or it loops forever |
Library sorts use Hoare-style scans, or a three-way partition (less, equal, greater) that puts all copies of the pivot in their final place at once. See also Quick Sort vs Merge Sort for quick sort's call stack, Heap Sort vs Quick Sort for the sorted-input worst case of a first-element pivot, and Comparison Sorting for quick sort next to the simple sorts.
Library sorts often use a three-way partition that puts every copy of the pivot in its final slot in one pass.
What the page leaves out
Other pivot rules (first, last, random, median of three), dual-pivot quick sort (Java's sort for primitive arrays), Lomuto variants that skip the self-swap when i = j, branch-free partitions, and switching to insertion sort for small ranges.
See where this page fits on the Sorting mind map.