Cycle Sort

Writes each element exactly once to its final position by counting how many items are smaller — the minimum possible number of writes.

Category: Sorting
Time complexity: O(n²)
Space complexity: O(1)

Pseudocode

for each start position
  count smaller items → target index
  place item there, follow the cycle
  until the cycle closes

Reference implementation

for start in range(n - 1):
    pos = start + sum(a[i] &lt; a[start]
              for i in range(start+1, n))
    # rotate item into pos, follow cycle

Open the interactive Cycle Sort visualisation →