Cyclic Sort vs Hashing
Use cyclic sort when the values are a permutation of 1 to n, because then the array indexes itself and the answer comes out in O(n) time and O(1) space. Use a set or a count array when the values are not bounded that way.
A family of problems says you have n numbers in the range 1 to n, and asks which is missing, which is duplicated, or which appear twice. The hash answer works and costs O(n) memory. The intended answer uses the fact that the values and the indices come from the same range, so the array can hold its own bookkeeping.
Side by side
| Dimension | Cyclic sort | Hashing |
|---|---|---|
| Requires | Values bounded by the array length | Nothing |
| Time | O(n), each value placed at most once | O(n) |
| Extra space | O(1) | O(n) |
| Mutates the input | Yes, it reorders or signs the values | No |
| Several answers at once | Natural, scan for every misplaced index | Natural, scan the counts |
| Readability | Needs a comment, the swap loop is not obvious | Says what it means |
When to pick each
Cyclic sort
- Find the missing number, the duplicate, or all the numbers that never appear, with the range given as 1 to n.
- Interview follow-ups that ask for constant extra space after you give the hash answer.
- First missing positive, which is the hardest member of the family and needs exactly this placement trick.
Hashing
- Values outside the index range, including negatives and arbitrary integers.
- Input you must not modify, such as a shared array or a method contract that forbids it.
- Code where the clearer version matters more than the constant factor.
Writing the placement loop with an if rather than a while. One swap can bring another misplaced value into the current index, so the position has to be re-checked until it holds the right value, and an if moves on too early and leaves the array half sorted. The equal-value guard matters too: swapping two identical values forever is the usual infinite loop in this pattern.
Questions people ask
Why is XOR sometimes the answer instead?
For exactly one missing number it is cleaner. XOR of 1 to n against XOR of the array cancels every value that appears in both and leaves the missing one, in O(n) time and O(1) space, without reordering the input. It stops working as soon as two values are missing, where the result is the XOR of both and tells you neither.
What is the sign-marking variant?
Instead of swapping, negate the value at the index each number points to, using the sign bit as a visited marker. It keeps O(1) space and avoids the swap loop, at the cost of mangling the values, which have to be read as absolute values afterwards. It is the standard answer to find all duplicates in an array.
Does cyclic sort actually sort?
Yes, as a side effect, when the values are a complete permutation of 1 to n. Each value ends up at its own index, which is sorted order. The name comes from that: every misplaced value is part of a cycle, and each swap closes one step of it, which is why the total work is linear rather than quadratic.