Cyclic Sort

March 2026 · 20 min read

The Core Idea

Cyclic sort applies whenever an array contains numbers drawn from a known contiguous range, typically [1, n] or [0, n-1], where n is the array length (or close to it). The key insight is simple: every number has exactly one correct index, so you can place each value where it belongs by swapping.

Think of a shelf of numbered books that have been knocked out of order. Book 3 belongs in slot 3, Book 7 belongs in slot 7. You pick up the book in front of you, look at its number, and swap it directly into its correct slot. You keep doing this until the book in front of you is already correct, then move on. One pass through the shelf and every book is home.

The mapping from value to index:

After placing every number at its correct index, any position where the value does not match the expected number reveals a missing or duplicate value. This is the foundation for an entire family of interview problems.

The Algorithm

The cyclic sort algorithm uses a single pointer i that walks from left to right. At each position:

1. Compute the correct index for arr[i]. For [1, n] values, that is arr[i] - 1.
2. If arr[i] is not at its correct index, swap arr[i] with arr[correctIndex].
3. After the swap, arr[i] has a new value. Repeat from step 1 without advancing i.
4. When arr[i] is already in the right place (or is out of range, or is a duplicate), advance i++.

Why O(n)? Each swap places at least one element at its correct position, and a correctly placed element is never moved again. So there are at most n swaps total across the entire algorithm, giving $O(n)$ time regardless of how many inner swaps happen at any single index.

Step-Through Animation

Watch cyclic sort in action on the array [3, 5, 2, 1, 6, 4] with values in [1..6]. At each step, the algorithm checks whether arr[i] is at its correct position. If not, it swaps the value to where it belongs. Cells turn green once correctly placed. Use the Step button to advance one operation at a time.

Manual Walkthrough

Let us trace cyclic sort on [3, 5, 2, 1, 6, 4]. Values are in [1..6], so value v belongs at index v - 1.

C++ Implementation

The base algorithm is remarkably short. The inner loop keeps swapping until arr[i] lands in its correct slot:

#include <vector>
#include <algorithm>

// Cyclic sort for array with values in [1, n]
void cyclicSort(std::vector<int>& arr) {
    int n = arr.size();
    int i = 0;
    while (i < n) {
        int correct = arr[i] - 1;
        if (arr[i] >= 1 && arr[i] <= n
            && arr[i] != arr[correct]) {
            std::swap(arr[i], arr[correct]);
        } else {
            i++;
        }
    }
}

// After sorting: arr[i] == i + 1 for all valid positions

Find the Missing Number

Problem: Given an array of n distinct numbers in the range [0, n], find the one number that is missing.

Place each number at its correct index (value v goes to index v for the [0, n] variant). After sorting, scan to find the index where arr[i] != i.

Visual Walkthrough

Array: [3, 0, 1]. Range is [0, 3], so one number is missing.

int missingNumber(std::vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        // Value v belongs at index v (for [0, n] range)
        if (nums[i] < n && nums[i] != nums[nums[i]]) {
            std::swap(nums[i], nums[nums[i]]);
        } else {
            i++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i) return i;
    }
    return n;
}

// Example: [3, 0, 1] => missing = 2
// After sort: [0, 1, 3]. Index 2 has value 3, not 2.

Find the Duplicate Number

Problem: Given an array of n + 1 integers where each integer is in [1, n], find the single duplicate.

Cyclic sort with early detection. When a swap would place arr[i] at a slot that already holds the same value, that value is the duplicate.

Visual Walkthrough

Array: [1, 3, 4, 2, 2]. Values in [1, 4] but the array has 5 elements-one value must repeat.

int findDuplicate(std::vector<int>& nums) {
    int i = 0;
    while (i < (int)nums.size()) {
        int correct = nums[i] - 1;
        if (nums[i] != nums[correct]) {
            std::swap(nums[i], nums[correct]);
        } else {
            if (i != correct) return nums[i];
            i++;
        }
    }
    return -1; // should not reach here
}

// Example: [1, 3, 4, 2, 2]
// At some point arr[i]=2 but arr[1]=2 already => duplicate is 2

Find All Missing Numbers

Problem: Given an array of n integers where each is in [1, n], find all numbers in that range that do not appear.

After cyclic sort, scan every index. If arr[i] != i + 1, then i + 1 is missing.

Visual Walkthrough

Array: [4, 3, 2, 7, 8, 2, 3, 1]. After cyclic sort: [1, 2, 3, 4, 3, 2, 7, 8].

std::vector<int> findDisappearedNumbers(std::vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        int correct = nums[i] - 1;
        if (nums[i] != nums[correct]) {
            std::swap(nums[i], nums[correct]);
        } else {
            i++;
        }
    }
    std::vector<int> result;
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            result.push_back(i + 1);
        }
    }
    return result;
}

// Example: [4, 3, 2, 7, 8, 2, 3, 1]
// After sort: [1, 2, 3, 4, 3, 2, 7, 8]
// Missing at index 4 (missing 5) and index 5 (missing 6)

Find All Duplicates

Problem: Given an array of n integers where each integer is in [1, n] and some elements appear twice, find all the duplicates.

The mirror image of "Find All Missing." After cyclic sort, one copy of each duplicate occupies its correct slot. The other copy is stranded at a wrong index. Scan for positions where arr[i] != i + 1 and collect arr[i] as a duplicate.

Visual Walkthrough

Same array as above. After sorting, the values at mismatched indices are the duplicates.

std::vector<int> findDuplicates(std::vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        int correct = nums[i] - 1;
        if (nums[i] != nums[correct]) {
            std::swap(nums[i], nums[correct]);
        } else {
            i++;
        }
    }
    std::vector<int> result;
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            result.push_back(nums[i]);
        }
    }
    return result;
}

// Example: [4, 3, 2, 7, 8, 2, 3, 1]
// After sort: [1, 2, 3, 4, 3, 2, 7, 8]
// Duplicates: [3, 2]

When to Use Cyclic Sort

Cyclic sort is the right tool when all three of these conditions hold:

1. Contiguous range: The values come from a known range like [1, n] or [0, n-1].
2. In-place requirement: You need O(1) extra space.
3. Missing or duplicate detection: You need to find what is out of place after sorting.

Complexity Summary

All cyclic sort variants share the same fundamental complexity. The sort itself is $O(n)$ with $O(1)$ space. The post-sort scan is another $O(n)$. Total: $O(n)$ time, $O(1)$ space.

Key Takeaways

• Cyclic sort places each value at its "home" index in O(n) total swaps.
• Applicable when values come from a contiguous range and you need O(1) space.
• After sorting, mismatched indices reveal missing numbers, duplicates, or both.
• The swap condition arr[i] != arr[correct] prevents infinite loops on duplicates.
• Every swap puts at least one element in its final position, guaranteeing O(n) total work.