Lomuto vs Hoare Partitioning

Lomuto's and Hoare's schemes both partition a range around a pivot in O(n) time and O(1) extra memory, so either can sit inside quicksort; they differ in how many swaps they make and in what they do with items equal to the pivot. This card compares them on three inputs and gives the rule for choosing between them.

Lomuto's scheme has one index that scans the range and swaps every smaller item it meets towards the front, including items that are already where they belong. Hoare's scheme, from Tony Hoare's original quicksort of 1961, works from both ends. An index i moves right until it finds an item at least as large as the pivot, an index j moves left until it finds an item no larger than the pivot, and the two items are swapped; the indices carry on until they cross. Each swap fixes two misplaced items at once, and an item already on the correct side is never moved. Hoare's scheme also differs in what it returns. It does not put the pivot in its final place; it returns a dividing index, with every item up to it no larger than the pivot and every item after it no smaller, and quicksort recurses on both parts.

A run sorted 1,000 numbers three ways with each scheme and counted swaps and comparisons. Both took the middle item of each range as the pivot, so that sorted input is not the worst case for either, and the shuffled input came from a generator seeded with 42.

Read the table by row. On shuffled input Hoare made fewer than half as many swaps, and on sorted input none at all, because every item already sat on the correct side of the pivot. Of Lomuto's 4,449 swaps on sorted input, the run counted 3,938 that moved an item onto itself: the items smaller than the pivot are already at the front, so i and j advance together and each swap exchanges a slot with itself. Hoare made more comparisons on the first two inputs, because both its indices stop on items equal to the pivot, but a comparison only reads two items while a swap writes two.

The last row is the one that decides most choices. With every item equal, Lomuto sends them all to the right of the pivot, every partition leaves one side empty, and the sort makes 499,500 comparisons, n(n − 1)/2, its quadratic worst case. Hoare's indices stop on every equal item from both ends and swap them, which splits each range near its middle, and the sort stayed at 11,862.

Use Lomuto where clarity matters more than speed, or where the code needs the pivot's final index, as a simple quickselect does. Use Hoare in a sort that must be fast on real data, which is full of repeated keys. Where repeated keys dominate, use a three-way partition, also called the Dutch national flag partition after Edsger Dijkstra's version of it. It keeps items smaller than, equal to and larger than the pivot in three bands, and the middle band is finished, so an array holding one repeated value is sorted by a single partition.