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.

Keep going

Finished this one? 0 / 62 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

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

Keep going

Counting Sort →

Dutch National Flag →

Two Pointers →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.