Comparison-Sorting Lower Bound: Decision Tree and Kraft Strip (2D)

Every comparison is a fork. The flat tree is the algorithm's real decision tree (the sort is run on all n! orderings). Below it the leaves tile a strip of length 1 (Kraft), and a histogram shows how deep they sit against the bound log₂ n!.
Average comparisons, 400 seeded random inputs: orange = this sort, blue = log2 n!, grey = n log2 n.
Independent numerical checks
Each line compares two separate calculations; a FAIL would show here.
The science

A comparison sort learns about the input only through yes/no answers "is ai < aj?". Each run therefore walks a root-to-leaf path in a binary tree, and the n! possible orderings must end in n! different leaves (otherwise two orderings would get the same answer). A binary tree of depth h has at most 2h leaves, so

2^h >= n!   =>   h >= ceil(log2 n!)  ~  n log2 n - 1.4427 n
average depth >= log2 n!         (Kraft inequality: sum over leaves 2^-depth = 1)
log2 n! = sum_{k=2..n} log2 k;   Stirling: n log2 n - n log2 e + 0.5 log2(2 pi n)

Kraft strip. A leaf at depth d owns the interval of length 2-d of the unit strip below its path; for a complete decision tree (every internal node has two children) the leaves tile the strip exactly with total length 1. Shallow leaves are wide, deep leaves thin. Simplifications. The tree is the algorithm's real decision tree, built by running the sort on every one of the n! permutations and merging the comparison outcomes (left = "less", right = "not less"); it is not drawn from a formula. Only the number of comparisons is counted (not moves or memory); inputs have distinct keys; the bound applies to comparison sorts only (counting/radix sort escape it by not comparing). The tree is shown for n up to 6 (720 leaves); the graph uses seeded random permutations.

Checks. (1) Leaves = n!, every input sorted, Kraft sum = 1 for 3 algorithms and n = 2..6; (2) smallest h with 2^h ≥ n! is 0, 1, 3, 5, 7, 10 for n = 1..6; (3) worst depth ≥ the bound; (4) Stirling vs direct log₂(100!); (5) new in this 2D view: the strip intervals are contiguous and sum to exactly 1 in integer arithmetic, and the histogram counts sum to n!. Node and leaf icons are Blender renders of the 3D page's models.

Made with 🟠 Blender