Why does Lomuto's partition perform more swaps than Hoare's on duplicate-heavy input?

## Two schemes, two invariant shapes Both schemes turn a collection into two regions around a pivot value in one linear pass with constant extra space. They differ in the shape of the invariant they maintain, and that shape is what drives the swap count. **Lomuto** is the single-sweep scheme. It keeps two indices moving in the same direction: a scan index `j` walking every position, and a boundary index `i` marking the end of the "at most the pivot" prefix. The invariant is one-sided: - `p[lo .. i]` — elements that compare at most equal to the pivot; - `p[i+1 .. j-1]` — elements that compare greater; - `p[j .. hi-1]` — unexamined. Because `i` trails `j` through a single left-to-right sweep, `i <= j` holds by construction — the two indices **cannot cross**. A final swap moves the pivot into the slot just past the boundary, so Lomuto genuinely leaves the pivot at the index it would occupy in a fully sorted collection. **Hoare** is the two-ended scheme. One pointer advances from the left until it finds an element that does not belong on the left, the other retreats from the right until it finds one that does not belong on the right, and then a single exchange repairs both. The invariant is two-sided: a settled prefix, a settled suffix, and an unexamined middle that shrinks from both directions. The pointers meet or **cross** in the middle, and the crossing point is what the pass returns. Crucially, Hoare's return value is a *split index*, not the pivot's final home — the pivot value may sit anywhere within either region. Code written for one scheme's return convention and run against the other will drop or double-count an element. ## Where the swaps go Lomuto's swap is inside the accepting branch: every element compared at most equal to the pivot causes `i` to advance and an exchange to happen. On distinct, well-mixed data roughly half the elements take that branch. On duplicate-heavy data — a run of records that all carry the same key as the pivot — nearly every element takes it, so the pass performs close to one exchange per element. Many of those are self-swaps where `i` and `j` have converged, and a self-swap is not free: it still executes the reads and writes of a real exchange, which for anything larger than a machine word is real memory traffic. Hoare's swap only fires when *both* pointers have stopped, meaning two elements are known to be on the wrong sides; the single exchange fixes both at once. Its scanning loops stop on elements that compare equal to the pivot rather than skipping them, which looks wasteful but has the effect of distributing equal elements across both regions instead of heaping them into one. Averaged over random input, the usual figure quoted for Hoare is about three times fewer swaps than Lomuto; both schemes make roughly one comparison per element, so the difference is in data movement, not in comparison count. Where elements *equal* to the pivot land is therefore a visible difference in the invariants, not an implementation detail: Lomuto sweeps them all into one region, Hoare splits them. That changes how evenly the collection is divided, which any divide-and-conquer caller feels directly. ## Defending the choice The skeptic's position — "Lomuto is simpler, so use Lomuto" — is not wrong, it is incomplete. Lomuto's one-sided invariant is genuinely easier to state, prove and get right under whiteboard pressure, and its final swap giving the pivot's true index makes callers simpler too. On distinct keys of small size, the extra swaps rarely dominate anything. The argument turns when the data has many repeated keys, or when the elements are large records whose movement is expensive, or when the caller depends on the split being even. Then the two-ended scheme's fewer moves and better distribution of equals are worth its fussier invariant — and if repeated keys dominate the workload, the honest answer may be neither scheme, but the three-way split that groups equals into their own region. ## What interviewers listen for Not the code. They listen for whether you can state each invariant mid-pass, say which pointers may cross and why, say what the returned index means in each scheme, and then connect the swap counts to the invariant shape rather than reciting "Hoare is faster". A candidate who says the two are interchangeable has not looked at what either one returns.