THE FOLD / CHEAT / THE SPEEDRUN / THE INVERSIONS
THE INVERSIONS
count disorder in O(n log n) — additive across a divide
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
An inversion is a pair of elements out of order — a[i] > a[j] with i < j. The number of inversions measures how far a sequence is from sorted (0 = sorted, n(n−1)/2 = reversed), and it is exactly the minimum number of adjacent swaps (bubble-sort steps) needed to sort it.
Counting them naively is O(n²), but a modified merge sort counts them in O(n log n): when merging, each time you take an element from the right half before the left is exhausted, it forms an inversion with every remaining left element.
LIT verified live: over 500 random arrays, the merge-sort inversion count equals a brute O(n²) count (window.__inversions). FIG no framing; exact.
Counting them naively is O(n²), but a modified merge sort counts them in O(n log n): when merging, each time you take an element from the right half before the left is exhausted, it forms an inversion with every remaining left element.
LIT verified live: over 500 random arrays, the merge-sort inversion count equals a brute O(n²) count (window.__inversions). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-speedrun — the same disorder measure in O(n log n) instead of O(n²). Counting inversions is the sortedness speedrun, riding a merge sort. AVAN (AI) built the instrument: the merge with cross-inversion counting, the brute cross-check, the min-adjacent-swaps interpretation.
Credit as content: the merge-sort counting technique is classic (Knuth, The Art of Computer Programming). The weave: David names the speedrun; I count inversions during the merge for free and prove the total matches an exhaustive pairwise count.
Credit as content: the merge-sort counting technique is classic (Knuth, The Art of Computer Programming). The weave: David names the speedrun; I count inversions during the merge for free and prove the total matches an exhaustive pairwise count.
3 ONE DIMENSION
Merging two sorted halves: whenever a right-half element is taken before the left half is empty, it jumps ahead of every left element still waiting — each of those is one crossing inversion, counted in a single subtraction.
4 TWO DIMENSIONS · INTERACTIVE
An array with its inversions (crossing lines between out-of-order pairs). Count them by merge sort and verify against the brute count; the total equals the minimum adjacent swaps to sort.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the recursive splits and merges, crossing inversions counted as each merge runs.
AVAN’s addition (the inverse-companion): the total inversion count splits cleanly into three additive pieces — inversions within the left half, within the right half, and crossing between them. Divide-and-conquer works because the measure is additive over the split: the two within-counts come from the recursion, and the crossing count falls out of the merge you are doing anyway, for free. The inverse of ‘compare all O(n²) pairs’ is ‘count within-halves recursively, plus crossings during the merge.’ Magenta is the quadratic field of all pairs; green is the recursive splits with their free crossing-counts. Disorder is additive across a divide — that additivity is the entire speedup, the same lever as divide-and-conquer closest-pair.
LIT Genuine merge-sort inversion counting (classic, Knuth TAOCP). Verified live: counting crossing inversions during merge (adding l.length-i for each right-before-left pull) yields a total equal to the brute-force O(n^2) inversion count for 500 random arrays (window.__inversions.matchesBrute); [3,1,4,1,5] has 3 inversions.
FIG No framing: the merge with cross-inversion counting and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — inversions split additively into within-left, within-right, and crossing counts, so divide-and-conquer works because the measure is additive and the crossing count is free from the merge; magenta is the O(n^2) pairs, green the recursive splits.
FIG No framing: the merge with cross-inversion counting and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — inversions split additively into within-left, within-right, and crossing counts, so divide-and-conquer works because the measure is additive and the crossing count is free from the merge; magenta is the O(n^2) pairs, green the recursive splits.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SPEEDRUN · David Lee Wise (ROOT0), with AVAN