Cycle sort

O(n²)

Cycle sort works out exactly where each value belongs by counting how many elements are smaller, then writes it straight there — displacing whatever was in that slot, which it then places in turn, forming a "cycle". It is O(n²) in comparisons but does the fewest possible writes, which matters when writing is expensive (e.g. flash memory).

Array
Edit the input and press Play

How it works

  1. For the current start, count how many values are smaller — that is its final position.
  2. Write the value there, picking up whatever it displaces.
  3. Place the displaced value the same way, continuing the cycle until it returns to start.
  4. Move to the next start position and repeat.

Pseudocode

1cycleSort(a):                       # O(n²), minimal writes2  for start = 0 to n-2:3    item ← a[start]4    pos ← start + (count of a[i] < item, for i > start)5    if pos = start: continue         # already in place6    while item = a[pos]: pos++        # skip duplicates7    swap item with a[pos]             # place it, pick up the next8    repeat until the cycle returns to start