Any decision tree that sorts n elements has height

Claim: Any comparison decision tree that sorts n elements has height Ω(n log n).

Reason:

• A comparison decision tree must have a distinct leaf for each possible ordering of the input, so it must have at least n! leaves.

• A binary tree of height h has at most 2^h leaves. Therefore we must have 2^h ≥ n!, which implies h ≥ log2(n!).

• Lower bound for log2(n!):

  Compute log2(n!) = Σ_{i=1}^n log2 i. For i > n/2 each term is at least log2(n/2), so

  log2(n!) ≥ (n/2) · log2(n/2) = (n/2)(log2 n − 1) = Ω(n log n).

Combining these facts gives h ≥ log2(n!) = Ω(n log n), so the height of any decision tree that sorts n elements is Ω(n log n).