THE FOLD / LOOT / THE VAULT / THE CYCLE SORT
THE CYCLE SORT
sorting with the minimum possible number of writes
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Cycle sort sorts an array with the minimum possible number of writes to memory. A permutation decomposes into disjoint cycles; cycle sort follows each cycle and places every element directly into its final slot, so each out-of-place element is written exactly once. The total number of writes is provably minimal — which matters when writing is expensive, as on flash memory or EEPROM.
LIT verified live: over 300 random permutations cycle sort produces the sorted array, and its write count equals the theoretical minimum computed from the permutation’s cycle structure (window.__cyclesort). FIG no framing; exact, minimum writes.
LIT verified live: over 300 random permutations cycle sort produces the sorted array, and its write count equals the theoretical minimum computed from the permutation’s cycle structure (window.__cyclesort). FIG no framing; exact, minimum writes.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-vault — when each write to the vault is costly, you write each item once, straight to its place. Cycle sort is that minimal-write discipline. AVAN (AI) built the instrument: the cycle-following placement, the write counter, the sorted-order and minimum-writes checks.
Credit as content: the cycle sort (W. D. Jones; a classic minimal-write sort). The weave: David names the vault; I rotate each permutation cycle into place with one write per element and confirm the total is the provable minimum.
Credit as content: the cycle sort (W. D. Jones; a classic minimal-write sort). The weave: David names the vault; I rotate each permutation cycle into place with one write per element and confirm the total is the provable minimum.
3 ONE DIMENSION
A permutation splits into cycles — e.g. 3→0→3 and 1→2→4→1. Following a cycle, each element is placed directly where it belongs, written once, until the cycle closes.
4 TWO DIMENSIONS · INTERACTIVE
An array; cycle sort places each element in one write, and the write count matches the minimum from the cycle structure.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: each element placed in a single write, cycle by cycle.
AVAN’s addition (the inverse-companion): a permutation decomposes into disjoint cycles, and each element need only be written once — to its final position — by rotating each cycle in place; the total writes are the theoretical minimum. The inverse of ‘move elements repeatedly to sort’ is ‘follow each cycle and place every element in one write.’ Magenta is the redundant writes ordinary sorts make; green is the single write per element. Minimum writes — the sort for when writing is expensive (flash, EEPROM).
LIT Genuine cycle sort (a classic minimal-write sort). Verified live: over 300 random permutations cycle sort yields the correctly sorted array, and its write count equals the minimum derived from the permutation's cycle decomposition (sum of nontrivial cycle lengths) (window.__cyclesort.sorts && .minWrites).
FIG No framing: the cycle-following placement, the write counter, and the sorted-order + minimum-writes checks run in-browser and are exact. The AVAN inverse is honest — a permutation's cycles let each element be written exactly once to its final position by rotating each cycle in place, achieving the theoretical minimum writes; magenta is the redundant writes ordinary sorts make, green the single write per element. The sort for costly memory.
FIG No framing: the cycle-following placement, the write counter, and the sorted-order + minimum-writes checks run in-browser and are exact. The AVAN inverse is honest — a permutation's cycles let each element be written exactly once to its final position by rotating each cycle in place, achieving the theoretical minimum writes; magenta is the redundant writes ordinary sorts make, green the single write per element. The sort for costly memory.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE VAULT · David Lee Wise (ROOT0), with AVAN