A multi-key table sort is not the comparison. It is what happens to the rows the comparison cannot separate. Return 0 for two rows and their arrangement is decided by whatever the query plan felt like that morning — invisible on one screen, fatal across two pages, because a sort has to be a total order or the same rows come back differently every time the query does.
The clause that makes it total is the last one, and the last one is the one people delete:
if (r) return dir * r; // a key separated them
}
if (o.tie) return a.id < b.id ? -1 : a.id > b.id ? 1 : 0; // the deleted line
return 0;
Seven implementations differing by one clause each, scored against an oracle that never compares two rows: https://dev48.infy.uk/design/day72-multi-key-sort.html
The fixture cannot tell any of them apart
On a hand-written fixture — a handful of rows, every value different, nothing blank — all seven produce the byte-identical order on 100.0% of 800 cases, across all six sort specs. Not nearly all. 800 of 800, six of six, correct machine and six broken ones indistinguishable.
The blindness is arithmetic rather than statistical. Sweep row count and the three defects the fixture could ever see switch on at exact sizes: first-key-only at 6 rows, sort-then-reverse at 10, and the missing tie-break together with the unstable quicksort at 21 — which is lcm(5,4)+1, the first row count at which two rows can tie on both keys of the board spec at all. The other two are unreachable at any row count, because the fixture has no blank cells and no multi-digit numbers.
Only one class of defect duplicates a row
| defect, 300 real boards, 20 rows a page | exact order | rows shown twice | rows never shown |
|---|---|---|---|
| no tie-break | 42.0% | 279 | 465 |
| unstable quicksort | 44.7% | 276 | 467 |
| sort then reverse | 41.3% | 0 | 682 |
| first key only | 13.3% | 0 | 551 |
| blank counts as zero | 51.0% | 0 | 941 |
The four deterministic defects duplicate nothing. Query page one and page two and they agree with each other perfectly, and merely hand back the wrong forty rows. Only a non-total order makes a row appear on both pages while another appears on neither.
What the measurement contradicted
I drafted the ascending/descending/ascending round trip as the property that would catch a missing tie-break — click a header, click it twice more, you should be looking at the first screen again. It is blind to it by construction. The no-tie-break machine passes 150 of 150 on every corpus, 100.0%, because flipping a direction never changes which rows are tied: a comparator returning 0 returns 0 both ways, and the sort's own stability carries the arrangement back unchanged.
The round trip does separate something — the quicksort, down to 50 of 150 on the seams corpus. Which is a different bug, and reading that as coverage is exactly the mistake.
4,340,301 assertions on load against a rank-vector oracle, plus 1,648 in the extracted-engine verifier. Self-contained: one file, inline CSS, no external asset of any kind.
Part of a from-scratch series — one component a day, vanilla JS, dependency-free engine: https://dev48.infy.uk/designfromzero.php
Top comments (0)