1. Introduction

Cyclic Sort is a highly efficient in-place sorting pattern for arrays where:

• The array contains numbers in a specific range, usually 1 to n or 0 to n-1.
• Each number is unique, or there might be duplicates but still within a known range.

The key idea is:

Place each number at its correct index (e.g., number 1 at index 0, number 2 at index 1, …).

Unlike general sorting algorithms like quicksort or mergesort, Cyclic Sort achieves O(n) time complexity without extra space if the constraints fit.

It is extremely useful in problems where you need to detect missing numbers, duplicates, or misplaced numbers.

2. When to Use Cyclic Sort

Cyclic Sort is ideal when:

1. Array contains numbers from a known range (usually 1 to n or 0 to n-1).
2. You need to find missing numbers, duplicates, or misplaced elements.
3. You want a linear time solution without extra space.
4. Indexes in the array can directly correspond to values, making swaps meaningful.

Problem Indicators

• “Find missing numbers in range 1…n”
• “Find duplicates in 1…n”
• “Sort array in-place where numbers are in 1…n”
• “Find first missing positive integer”

Real-World Analogy

Imagine a row of mailboxes numbered 1 to n, and each letter has a number.
Cyclic Sort is like placing each letter in its correct mailbox directly, instead of comparing every letter with every other one.

3. Core Idea

1. Iterate through the array.
2. For each element at index i, check if it is at its correct index (nums[i] == i+1 for 1-based numbers).
3. If not, swap it with the element at its correct index.
4. Continue until all elements are in their correct positions.

Key Insight

• A number x belongs at index x - 1 (1-based).
• Swapping directly moves elements to their correct positions.
• Because each swap places at least one number correctly, the algorithm runs in O(n).

4. Step-by-Step Example

Input

nums = [3, 1, 5, 4, 2]

Step 1: Start at index 0

• nums[0] = 3
• Correct index = 2 (3 → index 2)
• Swap nums[0] and nums[2] → [5, 1, 3, 4, 2]

Step 2: Check index 0 again

• nums[0] = 5
• Correct index = 4
• Swap nums[0] and nums[4] → [2, 1, 3, 4, 5]

Step 3: Check index 0 again

• nums[0] = 2
• Correct index = 1
• Swap nums[0] and nums[1] → [1, 2, 3, 4, 5]

Step 4: Check remaining indices

• nums[1] = 2 (correct)
• nums[2] = 3 (correct)
• nums[3] = 4 (correct)
• nums[4] = 5 (correct)

All numbers are now at their correct indices → array is sorted.

5. Java Implementation – Sorting Array with Cyclic Sort

public class CyclicSort {
    public void cyclicSort(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            int correctIndex = nums[i] - 1;
            if (nums[i] != nums[correctIndex]) {
                // Swap nums[i] with nums[correctIndex]
                int temp = nums[i];
                nums[i] = nums[correctIndex];
                nums[correctIndex] = temp;
            } else {
                i++;
            }
        }
    }

    public static void main(String[] args) {
        CyclicSort cs = new CyclicSort();
        int[] nums = {3, 1, 5, 4, 2};
        cs.cyclicSort(nums);
        System.out.println(Arrays.toString(nums)); // Output: [1, 2, 3, 4, 5]
    }
}

6. Time and Space Complexity

• Time Complexity: O(n)
  Each number is swapped at most once into its correct position.
• Space Complexity: O(1)
  Sorting is done in-place, no extra arrays are used.

7. Variants and Problem Applications

7.1 Find Missing Number

Problem: Array of numbers from 1 to n with one missing number.
Input: [4, 3, 1, 5]
Output: 2

Approach:

1. Apply Cyclic Sort to place numbers in correct positions.
2. Scan array to find index i where nums[i] != i + 1.
3. Missing number = i + 1.

public int findMissingNumber(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int correctIndex = nums[i] - 1;
        if (nums[i] <= nums.length && nums[i] != nums[correctIndex]) {
            int temp = nums[i];
            nums[i] = nums[correctIndex];
            nums[correctIndex] = temp;
        } else {
            i++;
        }
    }
    for (i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return nums.length + 1;
}

7.2 Find All Duplicates

Problem: Array of numbers 1…n may contain duplicates. Find all duplicates.

Approach:

1. Place numbers in correct indices using Cyclic Sort.
2. Numbers not in the correct index indicate duplicates.

Example:

Input: [4,3,2,7,8,2,3,1]
Output: [2,3]

7.3 Find All Missing Numbers

Problem: Array of numbers 1…n may have missing numbers.
Approach: Same as duplicates, scan for positions where nums[i] != i+1.

7.4 First Missing Positive

Problem: Find the first missing positive integer from an unsorted array.
Approach:

• Apply cyclic sort for numbers 1 to n.
• First index i where nums[i] != i+1 → i + 1 is the missing number.

8. Why Cyclic Sort is Efficient

• Unlike conventional sorting (O(n log n)), Cyclic Sort works in linear time for specific cases.
• In-place → O(1) space.
• Directly maps value to index, which allows easy identification of:
  • Missing numbers
  • Duplicates
  • Misplaced elements
• Ideal for range-constrained problems.

9. Key Takeaways

1. Use Cyclic Sort when array numbers fall in a known range and you need in-place sorting or anomaly detection.
2. Each number should ideally be at index = value – 1.
3. Swap numbers into correct positions until all numbers are sorted or placed correctly.
4. After sorting, any deviations (like nums[i] != i+1) indicate missing numbers, duplicates, or misplaced values.
5. Time Complexity = O(n), Space Complexity = O(1) → extremely efficient.

10. Summary of Steps

Step	Action
1	Initialize pointer i = 0
2	While i < n, check if nums[i] is at correct index
3	If not, swap with nums[correctIndex]
4	Else, increment i
5	After loop, array is sorted or anomalies are at mismatched indices

11. Real-World Analogy

Think of mailboxes numbered 1 to n and letters with numbers:

• You keep placing each letter into its correct mailbox.
• Letters that cannot be placed correctly indicate missing or duplicate numbers.