Definition
- Cyclic Sort – an in-place sorting technique for arrays whose values form a known contiguous range (typically 1 to n or 0 to n - 1).
- Home index rule – value v belongs at index v - 1 (for 1 to n range), so each value has exactly one correct position.
- Swap-until-correct – keep swapping the current element to its home index until the current slot holds the right value, then advance the pointer.
- Amortized O(n) – each swap settles at least one number permanently, and there are only n numbers, so at most n swaps total.
- Pattern family – the same place-at-index idea solves missing number, find all duplicates, and find the first missing positive.
Imagine the National Bank of India numbers its safe deposit lockers 1 to n, and at closing the keys are scattered on the counter. Key 5 belongs in locker 5, key 1 in locker 1. Rajesh picks up whatever key is in front of him, walks it to its matching locker, and takes whatever key was already there. He keeps swapping until the front slot holds the right key, then moves to the next slot. No key is carried twice unnecessarily, so the whole counter is tidied in one disciplined pass.
Understanding the Concepts
What is Cyclic Sort?
Cyclic Sort is an in-place linear-time sorting technique that works when the array values form a known contiguous range, typically 1 to n (or 0 to n - 1), and the values are distinct. The key insight is that each value has exactly one correct home index. For a 1-to-n array, value v belongs at index v - 1.
Instead of comparing elements against each other like a comparison sort, you simply carry each value to its rightful slot.
package com.bank.service;
// Values 1..5 shuffled: [3, 1, 5, 4, 2]
// Value 3 belongs at index 2
// Value 1 belongs at index 0
// Value 5 belongs at index 4
// After cyclic sort: [1, 2, 3, 4, 5]
How does the algorithm work internally?
Keep a pointer i at the current position. Compute the target index j = nums[i] - 1. If nums[i] is not at its target (nums[i] != nums[j]), swap nums[i] with nums[j]. Crucially, do not advance i after a swap because the element just moved into position i might itself be out of place. Only when nums[i] is already correct do you advance i.
package com.bank.service;
import java.util.Arrays;
public class CyclicSort {
public static void sort(int[] nums) {
int i = 0;
while (i < nums.length) {
int correctIndex = nums[i] - 1;
if (nums[i] != nums[correctIndex]) {
// Swap to home position
int temp = nums[i];
nums[i] = nums[correctIndex];
nums[correctIndex] = temp;
} else {
i++; // already in place, move on
}
}
}
public static void main(String[] args) {
int[] lockerKeys = {3, 1, 5, 4, 2};
System.out.println("Before: " + Arrays.toString(lockerKeys));
sort(lockerKeys);
System.out.println("After: " + Arrays.toString(lockerKeys));
}
}
Before: [3, 1, 5, 4, 2]
After: [1, 2, 3, 4, 5]
Why is it O(n) despite the nested feel?
Although the while loop and the inner swapping look quadratic, the amortized analysis shows O(n). Each swap places at least one number into its final correct index permanently. Since there are only n numbers, at most n swaps occur across the entire run. The pointer i advances n times in total. So the total work is at most 2n steps, which is O(n).
package com.bank.service;
public class SwapCountDemo {
public static void main(String[] args) {
int[] nums = {5, 4, 3, 2, 1}; // worst case: completely reversed
int swaps = 0;
int i = 0;
while (i < nums.length) {
int j = nums[i] - 1;
if (nums[i] != nums[j]) {
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
swaps++;
} else {
i++;
}
}
System.out.println("Swaps: " + swaps + " for n=" + nums.length);
}
}
Swaps: 2 for n=5
Why use value comparison instead of index comparison?
Comparing nums[i] != nums[j] rather than i != j makes the algorithm robust if duplicates ever appear. With duplicates, two positions might both want to hold the same value, and an index comparison would create an infinite swap loop between them. The value comparison detects that the target already holds the correct value and stops.
package com.bank.service;
import java.util.Arrays;
public class DuplicateSafety {
public static void main(String[] args) {
// Array with a duplicate (3 appears twice, 2 is missing)
int[] nums = {3, 1, 3, 5, 4};
int i = 0;
while (i < nums.length) {
int j = nums[i] - 1;
if (nums[i] != nums[j]) {
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
} else {
i++;
}
}
System.out.println(Arrays.toString(nums));
// [1, 3, 3, 4, 5] -> index 1 has 3 instead of 2, revealing the duplicate and missing
}
}
[1, 3, 3, 4, 5]
How does this pattern find missing numbers?
After cyclic sorting, every value that could be placed at its correct index is there. Any position where nums[i] != i + 1 reveals either a missing number (i + 1 is missing) or a duplicate (nums[i] is the duplicate).
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class MissingNumberFinder {
public static List<Integer> findMissing(int[] nums) {
// Cyclic sort
int i = 0;
while (i < nums.length) {
int j = nums[i] - 1;
if (nums[i] != nums[j]) {
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
} else {
i++;
}
}
// Find mismatches
List<Integer> missing = new ArrayList<>();
for (i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
missing.add(i + 1);
}
}
return missing;
}
public static void main(String[] args) {
int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
System.out.println("Missing: " + findMissing(nums));
}
}
Missing: [5, 6]
What are the edge cases?
- Already sorted:
[1,2,3,4,5]makes zero swaps; every element is already home. - Single element:
[1]is trivially sorted. - Two elements swapped:
[2,1]needs exactly one swap. - Range 0 to n-1: adjust the home index to
nums[i]instead ofnums[i] - 1.
package com.bank.service;
import java.util.Arrays;
public class CyclicEdgeCases {
public static void main(String[] args) {
int[] sorted = {1, 2, 3};
CyclicSort.sort(sorted);
System.out.println("Already sorted: " + Arrays.toString(sorted));
int[] single = {1};
CyclicSort.sort(single);
System.out.println("Single: " + Arrays.toString(single));
int[] swapped = {2, 1};
CyclicSort.sort(swapped);
System.out.println("Swapped: " + Arrays.toString(swapped));
}
}
Already sorted: [1, 2, 3]
Single: [1]
Swapped: [1, 2]
When should you use Cyclic Sort?
Use Cyclic Sort when the array values form a known dense range (1 to n, 0 to n-1) and you need O(n) time with O(1) space. Do not use it as a general-purpose sort; it only works when each value maps to a unique index.
- Finding the missing number in a 1-to-n array.
- Finding all duplicates in a 1-to-n array.
- Finding the first missing positive integer.
- Sorting sequence numbers that are a known permutation.
What about the banking use case?
At the National Bank of India, the nightly settlement batch delivers settlement sequence numbers guaranteed to be a permutation of 1 to n but arriving in random order. Rajesh uses Cyclic Sort to arrange them in a single disciplined pass with no extra memory, keeping the reconciliation window fast even on very large batches.
package com.bank.service;
import java.util.Arrays;
public class SettlementReconciler {
public static void main(String[] args) {
int[] sequenceNums = {5, 3, 1, 4, 2};
System.out.println("Received: " + Arrays.toString(sequenceNums));
CyclicSort.sort(sequenceNums);
System.out.println("Sorted: " + Arrays.toString(sequenceNums));
}
}
Received: [5, 3, 1, 4, 2]
Sorted: [1, 2, 3, 4, 5]
What are common interview follow-up questions?
- What if the range is 0 to n-1 instead of 1 to n? (Adjust the home index to
nums[i]instead ofnums[i] - 1.) - What if there are duplicates? (The value comparison guard prevents infinite loops; mismatches after sorting reveal duplicates.)
- Can this sort arbitrary arrays? (No, only arrays with a known dense value range.)
- What is the maximum number of swaps? (n - 1 in the worst case for a derangement.)
Visual Overview
Cyclic Sort: Place Each Value at Its Home Index
Home rule: value v → index v-1
Input: [3, 1, 5, 4, 2]
i=0: nums[0]=3, home=2, nums[0]!=nums[2] → swap(0,2)
[5, 1, 3, 4, 2] (3 is now at index 2 ✓)
i=0: nums[0]=5, home=4, nums[0]!=nums[4] → swap(0,4)
[2, 1, 3, 4, 5] (5 is now at index 4 ✓)
i=0: nums[0]=2, home=1, nums[0]!=nums[1] → swap(0,1)
[1, 2, 3, 4, 5] (2 at index 1 ✓, 1 at index 0 ✓)
i=0: nums[0]=1, home=0, nums[0]==nums[0] → advance i=1
i=1: nums[1]=2, home=1 → advance i=2
i=2: nums[2]=3, home=2 → advance i=3
i=3: nums[3]=4, home=3 → advance i=4
i=4: nums[4]=5, home=4 → advance i=5 → DONE
Result: [1, 2, 3, 4, 5] (3 swaps for n=5)
Key Takeaway
Cyclic Sort is an in-place linear-time technique that applies when the array values form a known dense range such as 1 to n. The defining insight is that each value has exactly one correct home index, namely value minus one, so instead of comparing elements against each other you simply carry each value to its rightful slot.
You keep a pointer at the current position, compute the target index from the value there, and swap it home if it is not already correct. Critically, you do not advance the pointer after a swap because the element that just arrived may itself be misplaced. The reason it runs in linear time is amortized: every swap permanently settles at least one number, and there are only n numbers, so at most n swaps ever occur.
Guard the swap with a value comparison rather than an index comparison, which keeps the loop safe even if duplicates appear. That same place-at-index habit is what powers the missing-number and duplicate-detection variants: after sorting, any position where nums[i] != i + 1 reveals the anomaly.
At the National Bank of India, Rajesh used this in the nightly settlement batch where sequence numbers arrived as a permutation of 1 to n. Cyclic Sort arranged them in a single disciplined pass with no extra memory, and the same pattern detected any missing sequence numbers immediately after sorting.
Remember one sentence: when values map to indices, swap each to its home and the whole array is sorted in at most n swaps.
---