Cyclic Sort

Range 1..n in O(n)

1:00

How to sort and search a 1..n array in O(n) time and O(1) space by sending each value directly to its home index.

By the end, you can

State the home-index rule (value v → index v-1) and explain why it enables a direct placement strategy.
Trace cyclic sort on a small array, tracking swaps and pointer advances.
Explain why the total swap count is bounded by n, making the algorithm O(n) despite its loop structure.
Explain why the swap guard compares `nums[i]` to `nums[home]` rather than to `i+1`, and describe the duplicate scenario that breaks the naive check.
Apply the post-sort scan to identify missing or duplicate numbers in a 1..n array.
Adapt cyclic sort to solve First Missing Positive by adding a range guard to handle out-of-range values.
Distinguish the interview Cyclic Sort pattern from classic Cycle Sort in terms of time complexity and applicability.
Recognize the three problem signals that indicate cyclic sort is the right tool.

Up next in Searching & Sorting