Cyclic Sort Made Simple: Learn the Basics and How It Works
Source: Dev.to
Cyclic Sort
Cyclic sort is an in‑place and unstable sorting algorithm that is specially designed to sort arrays whose elements lie in a known range, e.g. from 1 to N.
How does it work?
Consider the following array that we want to sort in ascending order:
The algorithm repeatedly selects an element and puts it at its correct index.
It starts with the first element (index 0).
-
Select the first element – 5
Its correct index is 4 (because the value 5 belongs at position 4).
-
Swap 5 with the element at index 4 (value 2)
-
Check the new element at index 0 – now 2
2 belongs at index 1, so it is not in the correct position. The control variable does not advance.
-
Swap 2 with the element at index 1 (value 4)
-
Now the element at index 0 is 4
4 belongs at index 3 → not correct.
-
Swap 4 with the element at index 3 (value 3)
-
Now the element at index 0 is 3
3 belongs at index 2 → still not correct.
-
Swap 3 with the element at index 2 (value 1)
-
Now the element at index 0 is 1 – it is in its correct position.
The algorithm increments the control variable to the next index (1) and repeats the same process.(image URL truncated for brevity)
The procedure continues until every element resides at its proper index, yielding a sorted array.
Key Points
| Property | Description |
|---|---|
| In‑place | No extra array is required; swaps are performed within the original array. |
| Unstable | Relative order of equal elements is not preserved (though the classic use‑case has distinct values). |
| Time Complexity | O(N) – each element is moved at most once to its correct position. |
| Space Complexity | O(1) – only a few auxiliary variables are used. |
| Ideal Input | An array containing the integers 1 … N (or any contiguous range that can be mapped to indices). |
When to Use Cyclic Sort
- When you know the range of values in advance (e.g., a permutation of
1..N). - When you need linear‑time sorting with O(1) extra space.
- For problems such as “find the missing number”, “find duplicates”, or “place each element at its correct index”.
💡 The correct index for an element is its value − 1, if the range of numbers in the array is 1 to N.
Space Complexity
As this algorithm is an in‑place sorting algorithm, it does not require any auxiliary space. Hence, its space complexity is O(1).
Time Complexity
We have two scenarios: the worst case and the best case.
Worst Case
The worst case happens when every number is in the wrong place in an array with a known range (say, 1 to N).
The sample array used above, [5, 4, 1 (truncated).