AlgoPlusAlgoPlus
Learn/Problem-Solving Patterns
Lesson

Cyclic Sort

When the values are a known range 1..n, each has one home (value v at index v−1). Swap each value home in place — no comparisons, O(n).

8 min read Watch it move Build it

Cyclic sort works only when the values are a known range like 1 to n, where every value has exactly one correct home: value `v` belongs at index `v − 1`. It walks the array and, whenever a value is in the wrong spot, swaps it straight home. Because each swap puts at least one value where it belongs, the whole array sorts in a single sweep — with no comparisons.

Precondition: values are 1..n
The magic depends on the 1..n constraint — the values being exactly the whole numbers 1 through n. That's what guarantees each value has a unique home index. On arbitrary values there's no fixed slot to swap to, and the pattern doesn't apply.

The one-sweep loop

  1. 1Sit at index i and look at the value there, v.
  2. 2Its home is index v − 1. If v is already home (i === v − 1), move on: i++.
  3. 3Otherwise swap v to its home index, bringing whatever lived there back to i.
  4. 4Do not advance i after a swap — re-examine the new value now sitting at i.
  5. 5Continue until i reaches the end.

A real trace: sort [3, 1, 5, 4, 2]

  1. 1i = 0: value 3 → home index 2. Swap with index 2 → [5, 1, 3, 4, 2]. Don't advance.
  2. 2i = 0: value 5 → home index 4. Swap with index 4 → [2, 1, 3, 4, 5]. Don't advance.
  3. 3i = 0: value 2 → home index 1. Swap with index 1 → [1, 2, 3, 4, 5]. Don't advance.
  4. 4i = 0: value 1 is home (index 0). Advance.
  5. 5i = 1..4: every value is already home. Done → [1, 2, 3, 4, 5].
Why this is where it shines: missing & duplicate
Once each value is home, any index i whose value isn't i + 1 exposes an anomaly — that's how cyclic sort finds a missing number or duplicate in O(n). Add a guard so equal values don't swap forever: only swap when the target slot doesn't already hold the same value.
// Array holds values in 1..n, one number missing (and one duplicated).
// Sort in place, then the first mismatch reveals both.
function findMissing(nums) {
  let i = 0;
  while (i < nums.length) {
    const home = nums[i] - 1;                 // value v belongs at index v-1
    if (nums[i] !== nums[home]) {             // guard against equal-value loops
      [nums[i], nums[home]] = [nums[home], nums[i]]; // swap home
    } else {
      i++;                                    // in place (or a duplicate) -> move on
    }
  }
  for (let k = 0; k < nums.length; k++) {
    if (nums[k] !== k + 1) return k + 1;      // this value never arrived
  }
  return nums.length + 1;
}

// findMissing([1, 2, 4, 4, 5]) -> 3   (index 2 holds 4, not 3)
OperationTimeSpace
Cyclic sort · each swap fixes ≥1 value → at most n swapsO(n)O(1)
Why O(n), not O(n log n)?
There are no comparisons to sort by — the home index is computed directly from the value. Each swap permanently lands at least one value, so there can be at most n swaps total, giving linear time.
Check yourself
In a 1..n array, where does the value 7 belong?