Introduction

The Cyclic Sort Pattern is a specialized sorting technique designed for arrays containing numbers in a known range.

Unlike traditional sorting algorithms, Cyclic Sort places every element directly into its correct index by swapping.

Most interview problems based on this pattern run in O(n) time with O(1) extra space.

This pattern frequently appears in coding interviews at Amazon, Microsoft, Google, Meta, Adobe, Walmart Global Tech, and many other product companies.

---

When Should You Use Cyclic Sort?

Use this pattern when:

• Numbers are within a known range.
• Elements should occupy their natural index.
• Finding missing numbers.
• Finding duplicate numbers.
• Finding the first missing positive.
• Finding corrupt pairs.
• Detecting disappeared numbers.

Typical constraints include:

Numbers from

1 ... n

or

0 ... n

---

Basic Idea

Every number belongs to one fixed position.

Example

graph TD
    Number_1["Number 1"] --> Index_0["Index 0"]
    Index_0["Index 0"] --> N_["-------------------"]
    N_["-------------------"] --> Number_2["Number 2"]
    Number_2["Number 2"] --> Index_1["Index 1"]
    Index_1["Index 1"] --> N_["-------------------"]
    N_["-------------------"] --> Number_n["Number n"]
    Number_n["Number n"] --> Index_n_1["Index n-1"]

Instead of sorting completely,

place each number directly into its correct position.

---

Example

Input

[3,1,5,4,2]

Correct positions

1 2 3 4 5

---

Visualization

Initial

Index

0 1 2 3 4

Array

3 1 5 4 2

Swap

3 ↔ 5

↓

3 1 2 4 5

Swap

3 ↔ 2

↓

2 1 3 4 5

Swap

2 ↔ 1

↓

1 2 3 4 5

Sorted.

---

Core Observation

For values in the range 1 to n:

Correct Index

value - 1

Example

Value	Correct Index
1	0
2	1
3	2
4	3
5	4

---

Algorithm

graph TD
    Start_i_0["Start i = 0"] --> Correct_Index["Correct Index"]
    Correct_Index["Correct Index"] --> nums_i_1["nums(i) - 1"]
    nums_i_1["nums(i) - 1"] --> Already_Correct["Already Correct?"]
    Already_Correct["Already Correct?"] --> Yes["Yes"]
    Yes["Yes"] --> Move_i["Move i"]
    Move_i["Move i"] --> No["No"]
    No["No"] --> Swap["Swap"]
    Swap["Swap"] --> Repeat["Repeat"]
    Repeat["Repeat"] --> End["End"]

---

Java Solution

public class CyclicSort {

    public static void cyclicSort(int[] nums) {

        int i = 0;

        while (i < nums.length) {

            int correctIndex = nums[i] - 1;

            if (nums[i] != nums[correctIndex]) {

                swap(nums, i, correctIndex);

            } else {

                i++;

            }

        }

    }

    private static void swap(int[] nums,
                             int first,
                             int second) {

        int temp = nums[first];
        nums[first] = nums[second];
        nums[second] = temp;

    }

    public static void main(String[] args) {

        int[] nums = {3,1,5,4,2};

        cyclicSort(nums);

        for (int num : nums) {

            System.out.print(num + " ");

        }

    }

}

Output

1 2 3 4 5

---

Internal Working

Iteration 1

graph TD
    N_3_1_5_4_2["3 1 5 4 2"] --> Swap["Swap"]
    Swap["Swap"] --> N_5_1_3_4_2["5 1 3 4 2"]

Iteration 2

graph TD
    N_5["5"] --> Correct_Index["Correct Index"]
    Correct_Index["Correct Index"] --> N_4["4"]
    N_4["4"] --> Swap["Swap"]
    Swap["Swap"] --> N_2_1_3_4_5["2 1 3 4 5"]

Iteration 3

graph TD
    N_2["2"] --> Correct_Index["Correct Index"]
    Correct_Index["Correct Index"] --> N_1["1"]
    N_1["1"] --> Swap["Swap"]
    Swap["Swap"] --> N_1_2_3_4_5["1 2 3 4 5"]

Completed.

---

Complexity Analysis

Operation	Complexity
Time	O(n)
Space	O(1)

Although swaps occur, each element is moved to its correct position at most once.

---

Why is Cyclic Sort O(n)?

At first glance,

multiple swaps appear expensive.

However,

every swap places at least one element into its final position.

Since each element reaches its correct position only once,

the total number of swaps is bounded by n.

---

Production Use Cases

Although Cyclic Sort is mainly an interview pattern, similar ideas are used in:

Database Validation

Verify sequential IDs efficiently.

---

Inventory Systems

Detect missing serial numbers.

---

Student Roll Numbers

Identify missing or duplicate roll numbers.

---

Banking

Validate sequential transaction identifiers.

---

Manufacturing

Detect missing product serial numbers.

---

Healthcare

Verify patient record IDs.

---

Logistics

Detect missing shipment numbers.

---

Common Problems Using Cyclic Sort

Problem	Difficulty
Cyclic Sort	Easy
Missing Number	Easy
Find All Missing Numbers	Easy
Find Duplicate Number	Medium
Find All Duplicates	Medium
Set Mismatch	Medium
First Missing Positive	Hard
Find Corrupt Pair	Medium

---

Common Mistakes

Using Cyclic Sort on Arbitrary Arrays

The numbers must belong to a known range.

---

Wrong Index Calculation

For

1...n

Correct index is

value - 1

For

0...n

Correct index is

value

---

Forgetting Duplicate Checks

When duplicates exist,

ensure swapping doesn't continue infinitely.

---

Incrementing Index Too Early

Increase

i++

only when the current element is already in its correct position.

---

Array Index Out of Bounds

Validate values before calculating the target index if the problem allows invalid numbers.

---

Interview Tips

Mention these observations:

• Cyclic Sort works only when numbers belong to a fixed range.
• It is not a general-purpose sorting algorithm.
• It places each number directly into its expected index.
• Many interview problems don't require returning the sorted array—they use the arrangement to detect anomalies.

---

Frequently Asked Interview Questions

1. What is Cyclic Sort?

Answer

Cyclic Sort is an in-place sorting algorithm that repeatedly swaps elements into their correct positions based on their values.

---

2. When should Cyclic Sort be used?

Answer

When the array contains numbers in a known continuous range such as 1...n or 0...n.

---

3. What is the time complexity?

Answer

O(n) because each element is moved to its correct position at most once.

---

4. What is the space complexity?

Answer

O(1) since sorting is performed in place.

---

5. Why is it called Cyclic Sort?

Answer

Elements are repeatedly swapped through cycles until every value reaches its correct position.

---

6. Why isn't Cyclic Sort used as a general sorting algorithm?

Answer

It only works efficiently when the input values belong to a fixed, known range. It cannot sort arbitrary values like Merge Sort or Quick Sort.

---

7. Which interview problems commonly use this pattern?

Answer

Missing Number, Find Duplicate Number, Find All Missing Numbers, First Missing Positive, Set Mismatch, and Find Corrupt Pair.

---

8. How is Cyclic Sort different from Selection Sort?

Answer

Selection Sort repeatedly finds the smallest element, while Cyclic Sort immediately places each value into its correct index using swaps.

---

9. What is the biggest mistake candidates make?

Answer

Incrementing the index before placing the current element in its correct position or failing to handle duplicates, leading to infinite loops.

---

10. Where is this idea useful in production?

Answer

Sequential ID validation, inventory management, serial number verification, logistics tracking, manufacturing systems, and data consistency checks.

---

Quick Revision

Topic	Summary
Pattern	Cyclic Sort
Input Requirement	Numbers in a Known Range
Correct Index	value - 1 (for 1...n)
Time Complexity	O(n)
Space Complexity	O(1)
Main Operation	Swap to Correct Position
Interview Frequency	⭐⭐⭐⭐☆

---

Key Takeaways

• Cyclic Sort is a specialized pattern for arrays containing numbers in a known range.
• Each number is placed directly into its correct position using swaps.
• The algorithm runs in O(n) time with O(1) extra space.
• Many popular interview problems, such as Missing Number and Find Duplicate Number, build on this pattern.
• Understanding the relationship between a value and its expected index is the key to mastering Cyclic Sort.

---