Definition

Cyclic sort exploits the fact that in an array of values 1..n, each value has a fixed home (index = value - 1). If the value we are looking at is not at home, we send it straight there; if it is, we move on.

Key Characteristics

• ✓Uses the 1:1 mapping between values 1..n and indices - value v always belongs at index v-1
• ✓Each value moves to its home only once - total swaps at most n, hence O(n)
• ✓In-place - sorts within the array using only swaps, no extra memory
• ✓Unstable, and usable only when values are restricted to the range 1..n

Time Complexity