Cyclic Sort

Before we start

By the end of this page you will be able to:

• See exactly why a number in the range 1..N already knows which index it belongs at.
• Explain out loud why swapping into place always terminates and never loops forever.
• Recognise this trick in "find missing number," "find duplicate," and "first missing positive" problems.

Stop at every Pause & Think box. Five seconds of genuine thought beats five minutes of passive reading.

Picture this first (no code yet)

That attendant's method — read the tag, swap if needed, repeat — is Cyclic Sort.

The actual problem

The simplest form: you are given an array containing every number from 1 to N exactly once, but in scrambled order. Sort it in-place.

input  : [3, 1, 5, 4, 2]
output : [1, 2, 3, 4, 5]

The key gift: the number k belongs at index k - 1 (because arrays are 0-indexed). Number 1 belongs at index 0, number 3 belongs at index 2, etc.

Every number already knows its home.

First, the slow way (so you feel the pain)

The instinctive answer: use a standard comparison sort.

arr.sort()   # O(n log n)

That works, but it ignores the most important fact about the input: the values are in the range 1..N. A general sort treats them as arbitrary numbers and pays O(n log n) for knowledge it could have gotten for free.

Cyclic Sort will do it in O(n) — faster than any comparison sort is theoretically allowed to be — precisely because it exploits the range constraint.

The turning point

Look at the number at position i = 0 in [3, 1, 5, 4, 2]. It is 3. Its correct home is index 3 - 1 = 2.

Swap arr[0] with arr[2]. The 3 goes to its home at index 2. Whatever was at index 2 (5) is now at index 0 — and it still has its tag, so it will eventually find its own home too.

We keep doing this from the same position i until the number currently sitting there is already at its correct index. Only then do we advance i.

This is the cloakroom attendant's method, written as an algorithm.

The one idea to remember

Watch it happen, frame by frame

Array: [3, 1, 5, 4, 2]. Correct home for value v = index v - 1.

i=0 → value 3, belongs at index 2. arr[2]=5 ≠ 3 → swap(0,2)
      [5, 1, 3, 4, 2]    (3 is now home ✓, but 5 is at i=0, still wrong)

i=0 → value 5, belongs at index 4. arr[4]=2 ≠ 5 → swap(0,4)
      [2, 1, 3, 4, 5]    (5 is now home ✓, but 2 is at i=0, still wrong)

i=0 → value 2, belongs at index 1. arr[1]=1 ≠ 2 → swap(0,1)
      [1, 2, 3, 4, 5]    (2 is now home ✓, and 1 landed at i=0)

i=0 → value 1, belongs at index 0. Already home! ✓ → advance i

i=1 → value 2, belongs at index 1. Already home! ✓ → advance i
i=2 → value 3, belongs at index 2. Already home! ✓ → advance i
i=3 → value 4, belongs at index 3. Already home! ✓ → advance i
i=4 → value 5, belongs at index 4. Already home! ✓ → advance i

Done: [1, 2, 3, 4, 5]  ✅

i=0 → value 2, home=1. arr[1]=3 ≠ 2 → swap(0,1) → [3, 2, 1, 5, 4]
i=0 → value 3, home=2. arr[2]=1 ≠ 3 → swap(0,2) → [1, 2, 3, 5, 4]
i=0 → value 1, home=0. Already home! → advance i
i=1 → value 2, home=1. Already home! → advance i
i=2 → value 3, home=2. Already home! → advance i
i=3 → value 5, home=4. arr[4]=4 ≠ 5 → swap(3,4) → [1, 2, 3, 4, 5]
i=3 → value 4, home=3. Already home! → advance i
i=4 → value 5, home=4. Already home! → advance i
Result: [1, 2, 3, 4, 5]  ✅

Now, the code — line by line

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct = nums[i] - 1          # where does nums[i] belong?
        if nums[i] != nums[correct]:   # is it already there?
            nums[i], nums[correct] = nums[correct], nums[i]   # swap it home
        else:
            i += 1                     # it's home (or a duplicate) — move on
    return nums

Every line maps to the cloakroom:

• correct = nums[i] - 1 — read the coat's tag; compute which hook it belongs on.
• if nums[i] != nums[correct]: — is that hook free (or holding a different coat)? If so, swap.
• nums[i], nums[correct] = nums[correct], nums[i] — hang this coat on its hook, bring the displaced coat to position i.
• else: i += 1 — this coat is already on the right hook (or two identical tags — a duplicate). Either way, advance.

Why does it always terminate?

Each swap places exactly one new number at its correct index — a position it will never leave. The numbers that are already home are never disturbed (we only swap to correct, never away from a home position).

So after at most n swaps, every position holds the right number and the loop ends.

Total swaps ≤ n. Total iterations ≤ 2n. Time: O(n). Space: O(1).

Why is it so fast?

A comparison sort (quicksort, mergesort) must compare elements to decide their order. Information theory proves you can't sort arbitrary numbers faster than O(n log n) using comparisons.

But we are not sorting arbitrary numbers. We know exactly where each number goes without any comparison — directly from its value. That's free information the problem hands us, and Cyclic Sort spends it perfectly.

n = 100,000
comparison sort  →  ~1,700,000 operations   (n log n)
cyclic sort      →  ~200,000 operations     (2n)

When should I reach for this? (the trigger list)

Reach for Cyclic Sort when you notice:

• The array contains numbers in a continuous range — usually 1 to N, sometimes 0 to N.
• You're asked to find a missing number, duplicate, or misplaced element — in O(n) time and O(1) space.
• The problem says "the array has N elements containing values in [1, N]" or similar.
• The brute-force involves a HashSet or sorting — and the interviewer hints "can you do O(1) space?"

If you see those cues, think: "each number knows its home — send it there."

The same trick in four disguises

Disguise 1 — Find the Missing Number (LC #268)

Array has N elements, values in [0, N], one number is missing. Sort cyclically (adjust for 0-indexed: value v belongs at index v). Then scan for the first position where nums[i] != i.

def missingNumber(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct = nums[i]                        # value v belongs at index v
        if correct < n and nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1

    for i in range(n):
        if nums[i] != i:
            return i
    return n                                     # missing number is N itself

Same skeleton — place each number at its correct index, then scan for the anomaly.

Disguise 2 — Find All Duplicates (LC #442)

Array has N elements, values in [1, N], some appear twice. After cyclic sort, any index where nums[i] != i + 1 reveals a duplicate (the number that should be there was pushed out by the impostor).

def findDuplicates(nums):
    i = 0
    while i < len(nums):
        correct = nums[i] - 1
        if nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1

    duplicates = []
    for i in range(len(nums)):
        if nums[i] != i + 1:
            duplicates.append(nums[i])           # the value here is the duplicate
    return duplicates

Disguise 3 — First Missing Positive (LC #41)

The "boss fight" of this pattern. Values can be outside [1, N] — ignore those during sorting.

def firstMissingPositive(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct = nums[i] - 1
        if 0 < nums[i] <= n and nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]   # only sort values in range
        else:
            i += 1

    for i in range(n):
        if nums[i] != i + 1:
            return i + 1                         # first gap in the positive sequence
    return n + 1

Same three-phase structure: sort what you can → scan for the first anomaly → return it.

def findCorruptPair(nums):
    i = 0
    while i < len(nums):
        correct = nums[i] - 1
        if nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    for i in range(len(nums)):
        if nums[i] != i + 1:
            return [nums[i], i + 1]   # [duplicate, missing]

Traps that catch beginners

Say it like a pro (interview one-liner)

"Since the values are in [1, N], each number implicitly knows its correct index — value v belongs at index v−1. I'll use Cyclic Sort: walk through the array, and for each position that holds the wrong value, swap it directly to its correct index. Each swap places at least one number permanently, so the total work is O(n) with O(1) space. After sorting, a single scan reveals any missing or duplicate."

while i < n:
    correct = nums[i] - 1
    if nums[i] != nums[correct]: swap(i, correct)
    else: i += 1

Check yourself

Practice problems

When you can solve First Missing Positive from memory and explain why the guard exists, you've fully learned this pattern.

Next up: Matrix Spiral Traversal — where we peel a 2D grid layer by layer like an onion.