Cyclic sort can swap repeatedly without advancing its index — why is the total work still O(n)?

## The shape that misleads people Cyclic sort's placement loop repeatedly swaps *without* moving its cursor forward. Read locally, that looks like unbounded work per position, and the reflex answer — "a repeat-until-settled inside a walk over `n` slots is O(n^2)" — is the single most common wrong answer this pattern draws in interviews. The fix is to stop counting per position and count over the whole run instead. ## The counting argument Call a slot **settled** when it holds the value whose home it is. The claim is that every swap increases the number of settled slots by exactly one, and that a settled slot never becomes unsettled. *Every swap settles a slot.* A swap happens only when the value `v` at the cursor does not match what currently sits at `v`'s home. The swap deposits `v` into that home. By definition, that slot is now settled. *No swap unsettles a slot.* Suppose some slot `h` is already settled — it holds the value whose home is `h`. For a later swap to target `h`, the cursor would have to be holding a value whose home is also `h`, meaning the cursor's value equals the value already at `h`. But that equality is exactly the condition under which the loop *skips* the swap and advances instead. So a settled slot is never touched again. Put together: the settled count starts at zero or more, never decreases, increases by one per swap, and is bounded above by the number of slots. Therefore fewer than `n` swaps occur across the entire run. The cursor separately advances at most `n` times. Placement is O(n); the read-off pass afterwards is another O(n). Extra space is O(1) — the swaps happen inside the buffer. This is a potential-function argument in miniature: pick a quantity that only moves in one direction and is bounded, then charge each expensive step to a unit of it. ## Aggregate, not average Be precise about what kind of bound this is. It is not an average over random inputs, and it is not amortized in the sense of a data structure that occasionally pays a big cost and spreads it over cheap operations. It is a **worst-case aggregate bound**: for *any* arrangement of the licensed values, the total number of swaps is capped by counting settled slots. An adversary who gets to choose the arrival order gains nothing, because the counting argument never mentions the order. That distinction matters in a follow-up. If you say "O(n) on average", the natural next question is what the bad case looks like — and you will not be able to produce one, because there isn't one. ## Duplicates do not break the bound A reasonable worry: with duplicates present, some value has no home left, so surely the loop grinds. It does not. The guard skips whenever the destination already holds its own value, which is precisely what a second copy of an already-settled value encounters. The cursor then advances and the duplicate is simply left where it stands, to be reported by the read-off pass. Every swap that *does* happen still settles a slot, so the cap holds unchanged. ## The cost lens that actually matters Asymptotically this is linear, and it beats the Omega(n log n) floor that binds comparison sorts — legitimately, because it never compares two values to each other, only a value against the slot it is standing on. But the constant is not zero: the access pattern is a scatter. Sending values to arbitrary home indices jumps around the buffer, so the memory behaviour is worse per operation than a straight sequential pass. On small inputs the asymptotic win is invisible and a simpler approach may finish first; the linear bound is a promise about growth, not a promise of being fastest at every size. ## How to say it in an interview Three sentences is enough: each swap puts one value permanently home; a home is never vacated once filled, because the equal-value case is exactly the skip case; so total swaps are capped by the slot count and the whole thing is linear. Then add the qualifier that turns a good answer into a strong one — this holds for every input, not on average.