Cyclic Sort Pattern

CodingMid2 min read · 3 problemsUpdated Oct 28, 2026

Place each number at its index by swapping; O(n) sort when values are a known bounded range like 1..n.

When to Use It

Arrays containing values in range 1..n: find missing, find duplicate, find smallest missing positive.

Classic example: Find the missing number in an array of 0..n.

How It Works

When an array contains n integers drawn from a known dense range (typically 0..n-1 or 1..n), each value has a 'home' index. Cyclic sort walks the array and swaps each misplaced value into its home, leaving sorted positions as a side effect. Each swap places at least one element correctly, so total swaps are bounded by n: giving O(n) time and O(1) space, beating any comparison sort.

The placement-by-swap is what makes find-missing and find-duplicate problems trivial: after the pass, scan for the first index where a[i] != i (or a[i] != i+1), and you've found the gap or extra. No hash set, no extra array.

This only works when the value-to-index mapping is well-defined and dense. If values are sparse, negative, or larger than n, the swap target is undefined and the pattern fails. The classic 'first missing positive' problem cleverly ignores out-of-range values (placing them anywhere) because they can't be the answer.

Key Insight

Each swap places at least one element at its final index, so even though the inner loop looks O(n^2), total swaps across the whole array are bounded by n, yielding O(n) time and O(1) space without a hash set.

Each value goes to index value-1. Swap until in place, then advance.

Templates

int i = 0;
while (i < nums.length) {
    int correct = nums[i] - 1; // or nums[i] for 0..n-1
    if (nums[i] != nums[correct]) {
        int tmp = nums[i];
        nums[i] = nums[correct];
        nums[correct] = tmp;
    } else {
        i++;
    }
}
// now scan for the index where nums[i] != i + 1

i = 0
while i < len(nums):
    correct = nums[i] - 1  # or nums[i] for 0..n-1
    if nums[i] != nums[correct]:
        nums[i], nums[correct] = nums[correct], nums[i]
    else:
        i += 1
# now scan for the index where nums[i] != i + 1

Common Pitfalls

Using if instead of while in the inner loop: a single swap may bring another out-of-place value, which still needs placement.
Off-by-one between 0..n-1 and 1..n indexing: forgetting the -1 when computing target index for 1-indexed values.
Swapping when a[i] is already at its target (creating an infinite loop): the loop guard must check a[i] != a[a[i] - 1], not just a[i] != i + 1, to handle duplicates correctly.
Applying the pattern when values exceed n or are negative without first filtering them out.
For find-all-duplicates, returning during the swap phase rather than in a separate post-pass.

Variations

Find missing number in 0..n: cyclic sort, then scan for a[i] != i.
Find all duplicates / all missing in 1..n: cyclic sort then post-pass.
First missing positive: ignore values outside 1..n, then cyclic sort, then scan.
Sign-flip variant: mark seen indices by negating a[abs(x)-1] instead of swapping: same asymptotics, different style.

Big O

Time: O(n)
Space: O(1)

Each swap places a value at its correct index, and a value can be moved at most once, so total swaps are bounded by n. The reordering happens in place.

Next PatternIn-Place Reversal of LinkedList