THE CYCLE SORT the fewest writes possible — each element moved once, to its rank
When writing is the expensive operation — flash memory that wears out, EEPROM — you want the sort that writes each element at most once. Cycle sort does exactly that: an element’s final position is its rank (how many elements are smaller), so it follows the cycles of the permutation, placing each value directly where it belongs and displacing the one already there, until the cycle closes. The total number of writes is the theoretical minimum. It is slow in comparisons but optimal in writes — the sort you choose when every write costs. Placing [3,1,4,2,5] each at its rank yields the sorted order.
THE TECHNIQUE final position = rank; follow permutation cycles — minimal writes
The demo places each element of [3,1,4,2,5] at its rank (count of smaller elements) — the sorted order: live demo
HISTORY & CREDIT cycle sort · minimum writes
“Sorts all move things about the same.” — cycle sort writes each element at most once, the theoretical minimum. cited
the rank · an element’s final index is #(elements smaller) — its position is known directly. the cycles · place each value at its rank, displacing the one there, until the cycle closes. the writes · each element written at most once — the minimum possible; best when writes cost.
Every element sent straight to its rank along the permutation’s cycles — the fewest writes a sort can make. resource
RECOMMEND FOR I-13 placement by rank, on the compiler
On the canonical compiler, placing each element of [3,1,4,2,5] at its rank produces the sorted array:
$ i13 run or_cyclesort.i13 # place each element at its rank
RUN OK · 999 step(s) · peak stack 9 · call depth 11
is_sorted = 1 -- each value written to its rank position
Recommend as a NULL — resource, the minimum-writes kind. Cycle sort produces the same sorted output while minimizing writes — a specific resource optimization (B40), valuable only where writes are costly. No new invariant. NULL — the sort for wear-limited memory.