Cyclic SortEasyO(n) time · O(1) space

Cyclic Sort

Mahabharata — The Divine Order — Each Warrior to Their Rightful Position

स्वधर्मे निधनं श्रेयः परधर्मो भयावहः। प्रत्येकः स्वस्थाने तिष्ठेत् — तदा व्यवस्था सिध्यति॥

*Better to die in one's own dharma than to follow another's. Let each be in their rightful place — then order is achieved.*

The Story

An array contains numbers from 1 to n (one per number, no duplicates). The task: sort it in-place in O(n) time without extra space.

The naive approach — comparison sort — takes O(n log n). But we have a key advantage: we know EXACTLY where each number belongs. Number `x` belongs at index `x - 1`.

Yudhishthira decreed: "Every warrior must stand at their designated position. Warrior 1 at position 0, warrior 5 at position 4. If they're out of place, swap them to their correct position immediately."

Cyclic Sort algorithm: ``` i = 0 while i < n: correct = arr[i] - 1 // Where arr[i] should be if arr[i] != arr[correct]: // Wrong position swap(arr, i, correct) // Send it home else: i++ // Already at correct position, or duplicate ```

For `arr = [3, 1, 5, 4, 2]`: - i=0: arr[0]=3, correct=2. arr[0]≠arr[2] → swap → [5,1,3,4,2] - i=0: arr[0]=5, correct=4. swap → [2,1,3,4,5] - i=0: arr[0]=2, correct=1. swap → [1,2,3,4,5] - i=0: arr[0]=1, correct=0. arr[0]==arr[0] → i++ - i=1: arr[1]=2, correct=1. arr[1]==arr[1] → i++ ... continue to end. Result: [1,2,3,4,5] ✅

"Notice: we only increment i when the current element is already in its correct position," Yudhishthira noted. "Otherwise, we keep swapping (potentially many swaps per i), but the total number of swaps across all iterations is O(n) — each element reaches its final home at most once."

This is O(n) time, O(1) space — optimal for this class of problems.

The Sentry's First Instinct

Use any comparison sort like quicksort or mergesort. O(n log n) time. Doesn't exploit the structure of 1..n range.

java

void cyclicSortBruteForce(int[] arr) {
    Arrays.sort(arr);  // O(n log n)
}

Yudhishthira's Placement Wisdom

Each element x belongs at index x-1. Place it there immediately by swapping. Use a while loop (not for loop) since after a swap, we need to re-examine position i. Only advance i when current element is in its correct position.

java

void cyclicSort(int[] arr) {
    int i = 0;
    while (i < arr.length) {
        int correct = arr[i] - 1;  // arr[i] belongs at index correct
        if (arr[i] != arr[correct]) {
            // Swap arr[i] to its correct position
            int temp = arr[i];
            arr[i] = arr[correct];
            arr[correct] = temp;
        } else {
            i++;  // arr[i] is in its correct position
        }
    }
}

Step-by-Step Walkthrough

arr=[1,5,3,2,4]
i=0: 1→correct=0, match → i++
i=1: 5→correct=4, swap → [1,4,3,2,5] → i stays 1
i=1: 4→correct=3, swap → [1,2,3,4,5] → i stays 1
i=1: 2→correct=1, match → i++
... all match. Result: [1,2,3,4,5] ✅

Deep Insight

**Why O(n) total swaps?** Each swap places at least one element in its final correct position. An element can be swapped at most once to its correct position. After that, it's never moved again. Total swaps ≤ n.

**Why `arr[i] != arr[correct]` and not `i != correct`?** For arrays with duplicates (cs-3, cs-5), `arr[i] == arr[correct]` (same value at both positions) means we can't swap — it would loop forever. Using value comparison is essential.

**The while loop over for loop:** After a swap, position i has a new value that needs to be examined. A for loop would skip it. The while loop re-checks position i until it's correct.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n log n)	O(1)	Comparison sort
Optimal	O(n)	O(1)	Each element moved to its place at most once. O(n) swaps total despite nested while.

Pattern Recognition

✅ Array contains 1..n (or 0..n-1)
✅ Place each element at index = value - 1
✅ While loop, not for loop (re-check position after swap)
✅ Stop condition: arr[i] == arr[correct] (handles duplicates)

**LeetCode Trigger Phrases:**
→ "sort array" + range 1 to n
→ "in-place sort" + 1..n values
→ Any find-missing/duplicate problem with 1..n range

Bhagavad Gita 3.35

श्रेयान्स्वधर्मो विगुणः परधर्मात्स्वनुष्ठितात्। स्वधर्मे निधनं श्रेयः परधर्मो भयावहः॥

Better is one's own dharma, though imperfectly performed, than the dharma of another well performed. Better is death in one's own dharma; the dharma of another is fraught with danger.

Connection: Each number has its own 'dharma' — its natural rightful position at index value-1. The cyclic sort honors this: it sends each number home immediately, without detour. Just as the Gita teaches that each soul has its unique rightful path, the cyclic sort recognizes each element's predetermined destination and places it there directly — the shortest path to cosmic order.