Cyclic Sort

Cyclic Sort

When an array of length n contains numbers from a known, tight range, typically 1..n or 0..n−1, every number already "knows" where it belongs: value v belongs at index v − 1. Cyclic sort exploits that: walk the array and keep swapping each number into its home slot. It sorts in O(n) time with O(1) extra space, which general-purpose sorts can't do.

The pattern matters less as a sorting method and more for what it reveals afterwards: once every number is home, any slot holding the wrong number points directly at a missing or duplicated value. That makes it the go-to technique for "find the missing / duplicate / first missing positive" problems with an O(1)-space requirement.

The core loop

void cyclicSort(int[] nums) {            // values are 1..n
    int i = 0;
    while (i < nums.length) {
        int home = nums[i] - 1;           // where nums[i] belongs
        if (nums[i] != nums[home]) {      // its home holds something else → swap it home
            swap(nums, i, home);          // don't advance i: a new value just arrived at i
        } else {
            i++;                          // nums[i] is home (or its home already holds a copy)
        }
    }
}

Trace [3, 1, 5, 4, 2]: 3 goes to index 2, giving [5,1,3,4,2]. 5 goes to index 4, giving [2,1,3,4,5]. 2 goes to index 1, giving [1,2,3,4,5]. Now every position checks out, and i walks to the end.

Why it's O(n) despite the nested behaviour: every swap puts at least one number permanently into its home, and a number that's home is never moved again. So there are at most n swaps plus n increments of i.

The condition is nums[i] != nums[home], not i != home. If the home slot already holds the same value (a duplicate), comparing values stops you from swapping two equal numbers back and forth forever.

Missing Number (values 0..n, one missing)

With values 0..n in an array of length n, value v belongs at index v, and the value n has no slot, so skip it:

public int missingNumber(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int v = nums[i];
        if (v < nums.length && nums[i] != nums[v]) swap(nums, i, v);
        else i++;
    }
    for (int k = 0; k < nums.length; k++) if (nums[k] != k) return k;
    return nums.length;                       // everything 0..n−1 present → n is missing
}

Alternatives worth mentioning. Sum formula: n(n+1)/2 − sum(nums), where you use long to avoid overflow. XOR: XOR all indices and all values, and pairs cancel to leave the missing number. Both are O(n) time and O(1) space without modifying the array. For this particular problem they're the better answer. Cyclic sort shines on the harder variants.

Find All Disappeared Numbers (values 1..n, duplicates allowed)

public List<Integer> findDisappearedNumbers(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int home = nums[i] - 1;
        if (nums[i] != nums[home]) swap(nums, i, home); else i++;
    }
    List<Integer> missing = new ArrayList<>();
    for (int k = 0; k < nums.length; k++) if (nums[k] != k + 1) missing.add(k + 1);
    return missing;
}

After sorting, each wrong slot k means value k + 1 never appeared. And the value sitting in that slot is one of the duplicates, which gives you Find All Duplicates from the same scan, by collecting nums[k] instead.

First Missing Positive: the showcase problem

The answer is always in 1..n+1: with n slots, at best 1..n are all present. So ignore anything outside 1..n (negatives, zeros, huge values) and cyclic-sort the rest:

public int firstMissingPositive(int[] nums) {
    int n = nums.length, i = 0;
    while (i < n) {
        int v = nums[i];
        if (v >= 1 && v <= n && nums[v - 1] != v) swap(nums, i, v - 1);
        else i++;
    }
    for (int k = 0; k < n; k++) if (nums[k] != k + 1) return k + 1;
    return n + 1;
}

This is a well-known "hard" problem that becomes straightforward once you recognise that the answer's range fits the array's indexes.

Find the Duplicate Number: when you can't modify the array

Cyclic sort finds it (the first time a value's home already holds that value), but it rearranges the input, and the classic version of this problem forbids that. The intended answer then is Floyd's cycle detection: treat i → nums[i] as a linked list. A repeated value means two indexes point to the same node, which creates a cycle, and the cycle's entrance is the duplicate.

public int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[0];
    do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast);   // meet inside the cycle
    slow = nums[0];
    while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }            // meet at the entrance
    return slow;
}

That's O(n) time and O(1) space without touching the array. See Fast & Slow Pointers for why the second phase lands on the entrance.

When to use cyclic sort

• ✅ Values lie in a range that matches the indexes (1..n, 0..n−1, or can be filtered to it).
• ✅ The question is about missing, duplicated or misplaced values.
• ✅ O(1) extra space is required, and modifying the input is allowed.
• ❌ Values are arbitrary or sparse (for example up to 10⁹ in an array of 10): there are no natural home slots, so use a hash set or sorting.

Follow-up questions this topic invites — and their answers

Q: Why is cyclic sort O(n) when it has a loop that doesn't always advance? A: Each swap places at least one value in its final position, and placed values never move again. There can be at most n swaps, and i advances at most n times, so the total work is O(n).

Q: What prevents an infinite loop when there are duplicates? A: Comparing values (nums[i] != nums[home]) rather than indexes. If the home slot already contains the same value, we don't swap, and i moves on.

Q: When would you choose the sum/XOR trick instead? A: For "exactly one number missing" (or one duplicate with everything else present once), sum or XOR is O(n) time, O(1) space and doesn't modify the array, so it's simpler and safer. Cyclic sort is needed for multiple missing or duplicate values, or for "first missing positive".

Q: The array must not be modified. How do you find a duplicate in O(1) space? A: Floyd's cycle detection on the index-to-value mapping, or binary search on the value range (count how many numbers are ≤ mid: more than mid means the duplicate is in the lower half), which is O(n log n).

Q: How is cyclic sort different from counting sort? A: Counting sort uses an extra count array of size equal to the value range, O(k) space, and works for any small range with any number of duplicates. Cyclic sort uses the input array itself as the "buckets", O(1) space, which only works when the value range matches the array's indexes.