Cyclic Sort
Intermediate · 18 min read · Problem-Solving Patterns, Searching & Sorting
Values 1 to n each have a home index: find missing and duplicate numbers in O(n) time and O(1) space, and count minimum swaps.
Some arrays come with a promise: n numbers, each between 1 and n (or 0 and n − 1). That promise means every value has a home — value v belongs at index v − 1 — so the array can sort itself by swapping each value straight into its home. No comparisons, no extra memory, O(n).
The idea: every value has a home
Picture a row of numbered lockers and a pile of numbered bags dumped into them at random. To tidy up, open locker i. If the bag inside isn't locker i's, carry it to its own locker and swap it with whatever is there. You're now holding a different bag in locker i: check it the same way.
Read the slots: what's missing, what's doubled
When values can repeat (and some are therefore missing), placement ends with every present value at its home. Each slot that still holds the wrong number tells you two things at once: i + 1 never came home, so it's missing, and the value sitting there is a spare copy, so it's a duplicate.
When some values have no home
The template assumes every value has a valid home. Two classic problems break that, and the fix is the same: values without a home stay where they are.
The other in-place trick: sign marking
Cyclic sort isn't the only way to use the array as its own "seen" table. When values are positive, you can mark that v was seen by making nums[v − 1] negative. Nothing moves, so the original order survives, and flipping the signs back restores the input exactly.
Cycles: the minimum number of swaps
Why the name cyclic sort? Draw an arrow from each index to the index its value belongs at. In a permutation, every index has exactly one arrow out and one arrow in, so the arrows split into separate cycles: values chasing each other's seats in a ring.
Practice ladder
Interview questions
- Your cyclic sort has a while loop that doesn't always advance i. Why is it O(n) and not O(n²)?
- Cyclic sort, sign marking or a hash set: which would you use for Find All Numbers Disappeared?
- Why is the minimum number of swaps to sort a permutation n minus the number of cycles?
- Find the Duplicate Number has n + 1 values in 1 … n. Why doesn't cyclic sort solve it?
Further reading
Key takeaways
- Values in a range tied to the length (1 … n, 0 … n) mean every value has a home index; swapping each value home sorts the array in O(n) time and O(1) space.
- Swap while nums[i] != nums[home], and move i only when no swap happens. Comparing values, not indexes, is what makes duplicates safe.
- After placement, a slot i without i + 1 means i + 1 is missing and the value there is a duplicate.
- Values with no home (0, n, negatives, anything above n) stay where they are; for First Missing Positive the answer is always in 1 … n + 1.
- A permutation is a set of cycles; the minimum number of swaps to sort it is n − cycles, and cyclic sort achieves it.
- If the input must stay untouched, cyclic sort is out: use Floyd's cycle detection (one repeated value), XOR or the sum formula (one missing value), or a hash set.