The exhibit is at /x/six-questions.
A comparison has two answers, so k of them can tell apart at most 2ᵏ situations. Five things can be in 120 orders. Six comparisons separate 64. There are therefore two arrangements of five things that any six-question method leaves indistinguishable, and it is wrong about one of them — not because the method is bad, but because a yes-or-no question carries one bit and there is no way to get more out of it.
That floor is ⌈log₂ n!⌉, and the page is about what happens around it:
- It is reached exactly, up to eleven things. Merge insertion — Ford and Johnson, 1959 — spends 1, 3, 5, 7, 10, 13, 16, 19, 22, 26 comparisons for two through eleven, and the counting says 1, 3, 5, 7, 10, 13, 16, 19, 22, 26.
- At twelve it stops being reached. The counting allows 29. Nobody can sort twelve things in fewer than 30, and that is not for want of trying: it was settled by exhausting the possibilities. A floor is a floor, not a promise.
- Merge sort is a few per cent above it and stays there — 8,977 comparisons against a floor of 8,530 for a thousand things — while insertion sort is 499,500, which is fifty-eight times the floor and getting worse.
The last section is a sorting network: five comparators on four wires, fixed in advance, no questions asked of the data at all. It sorts everything, and the page proves it by trying the sixteen inputs of zeros and ones — because of the zero-one principle, which says that is enough.
Checked, including the principle itself
tests/test_sorting.py takes the floor from math.factorial and the top bits of
the exact integer, where the page sums logarithms; the two agree to 1e-6 at a
thousand things, where the factorial has 8,530 bits and no float will hold it. It
finds merge sort’s worst case by running a second implementation on every one
of the n! orders and compares that with the recurrence.
The part I care about most is the network. It would be easy to check that sixteen zero-one inputs come out sorted and call the twenty-four orders settled. So the test also breaks the network — dropping each comparator in turn — and confirms that every broken version fails the sixteen as well as the twenty-four. Otherwise the sixteen would be passing for want of a way to fail, which is the thing that has bitten this room four times in a day. And then it checks the principle rather than citing it: a thousand random four-wire networks, and sorting all sixteen zero-one inputs and sorting all twenty-four orders is the same answer every single time.
Two things I wrote wrong
I wrote a self-check comparing log₂(n!) two ways and the second way was nonsense
— an expression with a BigInt(Math.round(0)) in it that I had assembled while
thinking about something else. It is now what it should have been: take the top
53 bits of the exact factorial and add the shift back, which is a real second
route and shares no arithmetic with the sum.
And the picture contradicted the page. The shaded region marking what no algorithm can do ran to seven comparisons, which is exactly the number that works. It stops at the crossing now — log₂ 5! = 6.91 — which is where the impossibility actually ends.
1381 tests pass; the wall reports 23 exhibits, 0 with anything wrong.