Cyclic Sort

## The setup Imagine a gate agent auditing a boarding pile. There are `n` seat tokens, each stamped with a number from `1` to `n`, and they were scanned into a buffer in whatever order passengers walked up. Exactly one seat is unaccounted for, and one token got scanned twice in its place. You have to name the missing seat. The obvious answers are: sort the pile and look for the gap, or build a membership structure and probe `1..n` against it. Both work. Cyclic sort is the answer that uses a property those two throw away — the numbers on the tokens are not arbitrary labels, they are *addresses*. ## Value as address With values drawn from the dense range `1..n` and exactly `n` slots to hold them, there is one slot per possible value. That is the whole license. It lets you declare a **home**: value `v` belongs at index `v-1`. Nothing has to be compared to anything; each value already knows where it goes. The placement loop is short. Look at the current slot. Compute the home of the value sitting there. If that home already holds its own correct value, this slot is as settled as it will get, so move on. Otherwise swap the current value into its home — which evicts whatever was squatting there into the current slot, where you immediately repeat the process on the newcomer. You do not advance while you are still holding a value that has somewhere to be. When the walk reaches the end, the invariant is: **every value present in the buffer sits at its own home index.** Slots whose value never showed up hold something else — necessarily a duplicate of a value that *did* show up, since the buffer is still full and nothing was created or destroyed by swapping. ## Why one scan suffices Because the post-placement invariant is a per-index equation, checking it is a linear walk with no state: ``` for i in 0..n-1: if a[i] != i + 1: report i + 1 as absent, a[i] as the doubled value ``` The first index that fails the equation names the absent value directly. You never search, never probe a side structure, never compare two tokens to each other. The check is the answer. This is what people mean when they call the pattern "placement, then read-off". The clever half is the placement; the reporting half is deliberately dumb. ## What it costs and what it demands Time is O(n): the placement walk does a bounded amount of work in total (each swap permanently settles one value at its home, so swaps cannot exceed the number of slots), and the read-off is one more pass. Extra space is O(1) — the reordering happens inside the buffer you were handed. That O(1) is not free. It is paid for by three demands on the input: | Demand | Why it is required | | --- | --- | | Values in a dense bounded range | Otherwise `v-1` is not a valid slot number; there is no home to swap into | | One slot per candidate value | Otherwise the equation `a[i] == i+1` is not what a complete input looks like | | Permission to reorder in place | The pattern destroys the arrival order; if the caller still needs it, you cannot use this | Drop any one of them and the pattern is inapplicable, not merely slower. ## The off-by-one that bites The home formula depends on where the range starts. For values `1..n` the home of `v` is `v-1` and the completed state is `a[i] == i+1`. For values `0..n-1` the home of `v` is `v` and the completed state is `a[i] == i`. Mixing the two produces either an out-of-range read on the largest value or a report that is off by exactly one — and the second failure is worse, because it returns a confident wrong answer instead of crashing. Fix the convention before writing the loop and state it out loud in an interview. ## The mental model to carry away Sorting arranges values *relative to each other*. Cyclic sort arranges values *relative to their own numeric identity*. That is why it escapes the comparison framing entirely: it never asks "is this token bigger than that one", only "is this token home yet". When a problem hands you a dense bounded range and permission to mutate, that question is cheaper — and the read-off afterwards is free.