When values are a known range
A special family of problems gives you an array holding numbers from a small contiguous range, often one through the array length. Cyclic sort exploits the fact that each value has a natural home index, so you can sort without comparisons and without extra arrays.
Swapping into place
Walk the array with one index. For the current position, look at the value sitting there.
- Compute the home index that value belongs to.
- If the value is not already home, swap it to its home position.
- Repeat at the same position until the value there belongs, then advance.
Each swap puts at least one number into its final spot, so the total work stays linear even though a single position may swap several times.
Reading the result
After the pass, any position whose value does not match its index points to a missing number, a duplicate, or a misplaced entry. This makes cyclic sort the go to tool for finding the smallest missing positive, the duplicate in a near complete range, or all numbers that vanished.
Key idea
When values map directly to indices, swap each one to its home so missing and duplicate numbers reveal themselves with no extra memory.