Cyclic Sort

Cyclic Sort

Most sorting algorithms are general-purpose: they know nothing about the values they're sorting beyond how to compare them. Cyclic sort breaks that assumption in a productive way. When an array contains integers in the range [1, n] (or [0, n]), every element carries an implicit address: the index where it belongs. The value k should live at index k - 1. Cyclic sort exploits this to place every element in its correct slot in a single linear pass, spending $O(1)$ extra space.

The Core Insight

Think of the array as a set of labeled mail slots and a pile of letters. Each letter has a number printed on it telling you exactly which slot it goes in. You don't need to sort the pile. You just walk through the slots one by one, and whenever you find a letter in the wrong slot, you carry it to its correct slot, placing whatever was there back in your hand. You keep swapping until the letter in your hand belongs in the current slot, then you move to the next slot. Because each swap puts at least one element permanently in its correct place, the total number of swaps across the entire traversal is bounded by n.

Walked Example: [3, 1, 5, 4, 2]

Start at index 0. The value is 3, which belongs at index 2. Swap nums[0] and nums[2]:

[5, 1, 3, 4, 2]   (index 0 now holds 5, which belongs at index 4)

Still at index 0. Value is 5, belongs at index 4. Swap nums[0] and nums[4]:

[2, 1, 3, 4, 5]   (index 0 now holds 2, which belongs at index 1)

Still at index 0. Value is 2, belongs at index 1. Swap nums[0] and nums[1]:

[1, 2, 3, 4, 5]   (index 0 now holds 1, correct! advance to index 1)

Indices 1 through 4 already hold their correct values. The array is fully sorted in 3 swaps. No matter how scrambled the input is, you will never do more than n - 1 swaps total across the whole traversal, because each swap retires at least one element to its permanent home.

The Algorithm

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        j = nums[i] - 1          # where nums[i] should live
        if nums[i] != nums[j]:   # guard: don't swap if already correct
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    return nums

The guard condition nums[i] != nums[j] is critical. Without it, a duplicate value (say two 3s) would cause an infinite loop: you'd swap index i with index j = 2 forever because neither swap makes progress. The guard says: "if the destination already holds the right value, don't bother swapping; just move on." This handles both the already-correct case and the duplicate case with the same single check.

First Missing Positive

The most famous application is LeetCode 41. After placing all values in [1, n] at their correct indices (ignoring anything outside that range), you scan the array once more. The first index where nums[i] != i + 1 tells you the answer.

def first_missing_positive(nums):
    n = len(nums)
    i = 0
    while i < n:
        j = nums[i] - 1
        # Only place nums[i] if it's in [1, n] and not already home
        if 1 <= nums[i] <= n and nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    # Second pass: find the first gap
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

The extra range check 1 <= nums[i] <= n filters out values like 0, negatives, and values larger than n. None of those have a valid home in the array, so we skip them. If all of [1, n] are present, the answer is n + 1.

Find All Duplicates

Once you understand the post-sort scan, variations come naturally. Take LeetCode 442, where the array contains integers in [1, n] where each value appears once or twice. After cyclic sort, every slot that holds the wrong value reveals a duplicate: nums[i] != i + 1 means nums[i] has a twin that already claimed its correct index.

def find_all_duplicates(nums):
    n = len(nums)
    i = 0
    while i < n:
        j = nums[i] - 1
        if nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    result = []
    for i in range(n):
        if nums[i] != i + 1:
            result.append(nums[i])
    return result

Find Missing Number

With LeetCode 268, the array contains n distinct numbers in [0, n]. Adjust the target index to nums[i] (since 0 is a valid value and should go at index 0) and use n as the sentinel for the element that can't be placed:

def missing_number(nums):
    n = len(nums)
    i = 0
    while i < n:
        j = nums[i]
        if nums[i] < n and nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i:
            return i
    return n

Complexity

The time complexity is $O(n)$. The outer loop runs n iterations in the index-advance path. Each swap places one element permanently, and an element can only be swapped once, so the total number of swaps is at most n - 1. The overall work is therefore bounded by 2n operations. Space complexity is $O(1)$, since the sort is done in-place with only a couple of index variables.

The pattern is recognizable by two signals: the input is an array of integers, and the problem asks about missing values, duplicates, or correct placement within a bounded range. When both signals are present, cyclic sort is almost always the intended $O(n)$ / $O(1)$ solution.

Recognizing this pattern

You're probably looking at cyclic sort when:

• The array contains integers from a known range like [1..n] or [0..n].
• You need to find a missing value, a duplicate, or the first missing positive integer.
• The problem demands $O(n)$ time and $O(1)$ extra space.
• The values themselves can act as indices: index i "should hold" value i+1 or i.

Common templates:

• Place value at index: while nums[i] is out of place and in range, swap it home. Example: Missing Number.
• Scan for mismatch: after cyclic placement, return the first index where nums[i] != i+1. Example: First Missing Positive.
• Detect duplicate by collision: swap reveals a duplicate when the target slot already holds the value. Example: Find the Duplicate Number.
• Collect all missing/duplicates: one pass to sort cyclically, second pass to list every mismatch. Example: Find All Numbers Disappeared in an Array.