In cyclic sort over values 1..n, why must the swap guard compare values rather than indices?

## Two guards that look equivalent When you write the placement loop for a bounded range, you need a condition that decides between swapping and advancing. Two candidates read almost identically out loud: - **Index guard**: "if the cursor is not already standing on this value's home, swap it there." - **Value guard**: "if this value's home does not already hold the right value, swap it there." On a clean permutation of `1..n` — every value present exactly once — they behave the same and both terminate. On any input with a duplicate, the index guard hangs. ## The hang, traced Take a boarding pile of two tokens where the same seat was scanned twice: both slots read `2`. Under the index guard, the cursor sits at slot `0`, the value is `2`, its home is slot `1`, and `0` is not `1`, so it swaps. The two slots hold identical values, so the buffer after the swap is exactly the buffer before it. The cursor did not advance, because advancing is the other branch. The very next iteration reproduces the same state, forever. Nothing about this is exotic. Any input where two slots carry the same value and neither is already at that value's home reaches the same fixed point. The loop is not slow; it never terminates. ## Why the value guard is the right question The termination argument for this pattern rests on a quantity that only grows: the number of slots holding the value that belongs there. Every iteration must move that quantity or move the cursor. The value guard is precisely the test for "can this iteration grow the quantity?" — if the home already holds its own value, no swap can improve anything, so the only useful action is to advance. The index guard asks a *positional* question that is a proxy for the real one, and the proxy fails exactly when two slots carry equal values. Note that the value guard also subsumes the index case: when the cursor already stands on the home, the value there trivially equals itself, so the skip branch fires anyway. The value guard is strictly more correct, not merely different. ## What the duplicate leaves behind Under the value guard, the second copy of a duplicated value is never placed — it has no home left — so it stays wherever it happened to be when the cursor reached it. That is not a defect; it is the mechanism the read-off depends on. After placement, the slot whose value never arrived is occupied by exactly that stranded copy, so one scan reports both facts at once: the index names the absent value, the occupant names the doubled one. ## The other boundary error in the same neighbourhood Homes depend on where the range starts. For values `1..n` the home of `v` is `v-1` and the finished state is `a[i] == i+1`. For values `0..n-1` the home of `v` is `v` and the finished state is `a[i] == i`. Carrying the `-1` into a zero-based range either reads outside the buffer on the largest value or, worse, produces a confidently wrong report that is off by one. Say your indexing convention out loud before writing the loop; it is the first thing an interviewer checks after the guard. A related trap appears when the input may contain values *outside* the licensed range — an unrecognised token in the pile. The home computed from such a value is not a valid slot, so the loop must screen it before computing a home: values outside the range have no home, get skipped like duplicates, and are left in place. Forgetting that screen turns a bad input into an out-of-range access rather than a clean report. ## How to demonstrate this well Do not just recite the guard. Name a two-slot input, walk the two iterations, and point at the state that repeats. Then say what the guard is really testing — whether progress is possible at all — and note that it is also what makes the swap count provably bounded. An interviewer who asked about duplicates is checking whether you reason about termination, not whether you memorised a condition.