Cyclic sort sorts an array that contains the numbers 1..n (each exactly once) in O(n) time and O(1) space, without comparisons. Because value v belongs at index v-1, you scan with a pointer: if the current element isn't already home, swap it to its correct index; only advance the pointer once the element sitting there belongs there. Every value walks to its slot in one direction.

Why is cyclic sort O(n) despite the inner swaps?

Each swap places at least one element at its final correct index, and an element never leaves a correct position. There are n positions to fill, so at most n swaps happen across the entire run, plus at most n pointer advances — total O(n). The inner loop can swap several times but the global swap count is bounded by n.

What problems does cyclic sort solve?

It's the go-to pattern whenever an array holds values in a known range like 1..n: find the missing number, find the duplicate, find all numbers that disappeared, find the first missing positive, and find the corrupt pair (a duplicate plus a missing). After cyclic-sorting, any index i whose value isn't i+1 immediately reveals the anomaly.

What if the array has duplicates or values out of range?

The core loop still works: when the current element already equals the element at its target index (a duplicate), you can't make progress by swapping, so you just advance the pointer. Values outside 1..n (like 0 or numbers greater than n) are skipped by a range check. That handling is exactly what lets cyclic sort locate missing and duplicate numbers.

Algorithms · In-Place Sort

Every Number, Home.

Here’s a special array: it holds the numbers 1..n, each exactly once, just scrambled. That constraint is a gift — value v has a known address, index v-1. So skip comparisons entirely: pick up whatever’s under your pointer and swap it straight to where it belongs, over and over, until the slot is right. Every number walks home in O(n).

O(n) time · O(1) space · no comparisons · in-place

the constraint

Values are 1..n — so each has one correct index.

home index

Value v belongs at index v−1.

swap, don’t step

If the current value isn’t home, swap it there; only advance when it is.

anomaly finder

After sorting, any slot with the wrong value flags a missing or duplicate number.

cyclic_sort.js — swap each value home

Ready

An array of 1..n, scrambled. A pointer i sits at index 0. Press Step: if arr[i] isn’t already home (at index arr[i]−1), swap it there; if it is, advance the pointer.

pointer i

swaps

home

How it works

Ordinary sorts compare elements to decide order. Cyclic sort doesn’t need to — the value is the address. Standing at index i, you ask one question: is arr[i] already at its home index arr[i]−1? If not, swap it there (which drops whatever was there into your hand to deal with next). If yes, this slot is settled — step forward.

Look at the home index

For arr[i] = v, its home is v−1. Check what’s sitting there.

Not home → swap it home

Swap arr[i] with arr[v−1]. Now v is placed forever; you hold whatever it displaced. Don’t move the pointer — inspect the new arrival.

Already home → advance

If arr[i] is already at its correct index, step the pointer to i+1.

✓

Each swap settles one value

An element never leaves a correct slot, so ≤ n swaps total — the whole thing is O(n), comparison-free.

Time

O(n)

Space

O(1)

Comparisons

Swaps

≤ n

The code, and why it matters

# sort an array of 1..n in place, O(n), no comparisons def cyclic_sort(a): i = 0 while i < len(a): home = a[i] - 1 # value v belongs at index v-1 if a[i] != a[home]: # not home (and not a duplicate) a[i], a[home] = a[home], a[i] else: i += 1 return a # find the missing number: after sorting, the first index i # where a[i] != i+1 is missing. Duplicates: a[i] != i+1 too.

The real payoff isn’t sorting — it’s the anomaly detection it unlocks. Once every present value is home, any index whose value doesn’t match instantly reveals the missing number, the duplicate, or the first missing positive — all in O(n) time and O(1) space. That family of interview problems is cyclic sort wearing different hats.

Quick check

1. Why doesn’t the pointer advance after a swap?

2. Why is cyclic sort O(n) despite swapping inside the loop?

FAQ

What is cyclic sort?

An O(n), comparison-free way to sort an array holding the numbers 1..n, by swapping each value to its home index (value v → index v−1) until every slot is right.

What problems does it solve?

Find the missing number, find the duplicate, find all disappeared numbers, find the first missing positive, find the corrupt pair. After cyclic-sorting, mismatched slots reveal the anomalies in O(1) space.

Does it handle duplicates?

Yes — when the current value already equals the value at its target index, swapping can’t make progress, so the pointer advances. That stuck-at-a-duplicate slot is exactly how you detect the duplicate.

Isn’t this just counting sort?

They share the "value is the index" idea, but counting sort builds a separate count/output array (O(n) extra space). Cyclic sort works in place with swaps and O(1) space — and its byproduct is the anomaly detection counting sort doesn’t give you for free.

SOLVE IT YOURSELF

Solve it: sort 1…n by putting each value home

When the values are exactly 1…n, you do not need comparisons at all — every value already knows which index it belongs at. Write it in Python or TypeScript, running for real in your browser.

YOUR TASK

Implement cyclic_sort(nums): given a list containing the numbers 1…n in any order, return it sorted — in O(n), using swaps only, no comparison sort and no extra array.

HINTS — 5 IDEAS

The key fact: value v belongs at index v − 1. That is the whole algorithm.
Walk an index i. If nums[i] is not home, swap it to where it belongs — and do not advance i.
Only advance i once the value sitting at i is already correct. Each swap places at least one value permanently, so the total work is O(n) despite the nested feel.
Advancing after every swap is the classic bug: the value you just swapped in has not been checked.
Compare against nums[target] rather than against i + 1 — that form also terminates cleanly if duplicates ever appear, instead of looping forever.

CPython · WebAssembly

Keep going

Finished this one? 0 / 99 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Every Number, Home.

How it works

Look at the home index

Not home → swap it home

Already home → advance

Each swap settles one value

The code, and why it matters

Quick check

FAQ

Solve it: sort 1…n by putting each value home

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Look at the home index

Not home → swap it home

Already home → advance

Each swap settles one value

The code, and why it matters

Quick check

FAQ

Solve it: sort 1…n by putting each value home

Keep going

Counting Sort →

Dutch National Flag →

Two Pointers →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines