Sandbox · exhibit 0033

You cannot sort five things in six questions

Every comparison you make has two answers, so k of them can tell apart at most 2^k different situations. Five things can be in 120 orders, and six questions separate at most 64. No cleverness closes that gap — it is not about the algorithm, it is about how much a yes-or-no question can carry. The floor is ⌈log₂ n!⌉, it is reached exactly up to eleven things, and at twelve it stops being reachable: the counting allows 29 and thirty are needed.

Counting the answers

Sorting means picking one arrangement out of n!. Each comparison splits the possibilities in two, at best evenly, so after k of them you have at most 2ᵏ distinguishable outcomes. When 2ᵏ is smaller than n! there are two arrangements you have not told apart, and the sort is wrong on one of them.

n! arrangements 2ᵏ outcomes

things to sort ·

What sorts actually spend

The floor is one thing and the cost of a method you would write is another. Insertion sort compares every pair in the worst case. Merge sort spends T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + n − 1, which is a few per cent above the floor and stays there. Merge insertion — Ford and Johnson, 1959 — sits on the floor exactly, for as long as the floor can be sat on.

the floor merge insertion merge sort insertion sort

Where the floor stops being reachable

Up to eleven things, somebody has found a way to sort in exactly the number of comparisons the counting allows. At twelve the counting allows twenty-nine and nobody can do it in fewer than thirty — and that is not for want of trying: it was settled by exhausting the possibilities. The floor is a floor, not a promise.

things	n!	⌈log₂ n!⌉	best known	gap

A sort with no questions in it

A sorting network fixes every comparison in advance — the same pairs in the same order, whatever the data. This one puts four things in order with five comparators, which is the floor for four, and you can check that it works by trying all sixteen arrangements of zeros and ones: a network that sorts every one of those sorts everything, which is the zero-one principle, and it is why sixteen tries settle a question about all twenty-four orders.

What this page checks about itself

Every number here is computed in the browser. The merge sort figures are the recurrence and the exhaustive worst case over all n! orders, for as far as exhausting them is cheap, and the two are compared.