Why n log n Is a Floor
In short: any sort that decides order by comparing two items can be
drawn as a decision tree — one internal node per comparison, branching
yes/no, one leaf per possible final ordering. Sorting n distinct items has
n! possible orderings, so the tree needs at least n! leaves, and a binary
tree with L leaves needs depth at least ⌈log₂ L⌉. That makes
⌈log₂(n!)⌉ comparisons — which works out to Θ(n log n) — the fewest
any comparison sort can need in its worst case. Counting sort isn't a
counterexample: it never compares two items against each other, so the
argument doesn't apply to it at all.
Six lines print, one per leaf of the decision tree in the drawing above — the recursion's call depth is exactly how many choices (comparisons) it takes to pin down one ordering, and the deepest calls go 3 levels in.
Count the orderings of a photo lineup
Quarry's test suite checks a sort against every possible input order for
small n, to catch bugs that only show up on rare arrangements. Before it
can do that, it needs to know how many orderings exist, and the fewest
comparisons any correct sort could need to tell them all apart:
Doubling n from 5 to 10 barely doubles min_comparisons (7 to 22) — the
log in n log n is why sorting scales so much better than the n!
orderings it has to tell apart might suggest.
Insertion sort vs. the floor
Insertion sort (section 3) compares every new item against the ones already placed, one at a time. On a reverse-sorted input, that is its worst case — watch how far above the floor it lands:
Insertion sort on 5 reverse-sorted items uses 10 comparisons — the
⌈log₂(5!)⌉ floor is only 7. Insertion sort is genuinely O(n²) in the
worst case; it just doesn't try to get close to the information-theoretic
minimum, because each comparison only rules out one possibility (key is
bigger or smaller than this one neighbour), not half of everything still
unknown.
Merge sort nearly touches the floor
Merge sort's comparisons are more informative: each one decides which of two already-sorted runs the next output item comes from, closer to halving the remaining possibilities every time:
def counting_comparisons_merge_sort(arr):
comparisons = 0
def sort(xs):
nonlocal comparisons
if len(xs) <= 1:
return xs
mid = len(xs) // 2
left, right = sort(xs[:mid]), sort(xs[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
comparisons += 1
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:]); out.extend(right[j:])
return out
return sort(list(arr)), comparisons
print(counting_comparisons_merge_sort([5, 4, 3, 2, 1]))No correct comparison sort can beat the floor, ever — that is what "lower bound" means:
def beats_lower_bound(n, comparisons_used):
orderings = __import__("math").factorial(n)
min_comparisons = 0 if orderings <= 1 else __import__("math").ceil(__import__("math").log2(orderings))
return comparisons_used < min_comparisons
print(beats_lower_bound(5, 6), beats_lower_bound(5, 7), beats_lower_bound(5, 10))Quick practice
import math
print(math.factorial(4), math.ceil(math.log2(24)))import math
print(math.factorial(1), math.factorial(0))🎯 Your turn
Build sort_lower_bound(n): return {"orderings": ..., "min_comparisons": ...} — the number of possible orderings of n distinct items, and the
fewest comparisons any correct comparison sort could need in the worst case
to always identify the right one.
sort_lower_bound(3)→{"orderings": 6, "min_comparisons": 3}sort_lower_bound(1)→{"orderings": 1, "min_comparisons": 0}
Hint: orderings = math.factorial(n). When orderings <= 1 there is
nothing to distinguish, so min_comparisons is 0; otherwise it's
math.ceil(math.log2(orderings)).
Press ▶ Run, try the Live App chips, then ✓ Check.