Lower Bound Comparison Sorting

Every comparison-based sorter requires at least logarithmically many comparisons relative to n! in the worst case: the decision tree has n! leaves, so its height is bounded below by log2(n!).

Counting/Radix Sort bypass this by using more than comparisons (in restricted key universes).

Justify why pure comparison sorting cannot fall below the information-theoretical limit in the worst case. This opens the door to Counting/Radix if the key universe allows it.

Depth

A comparison sort can be modeled as a decision tree. Each comparison has possible outcomes and splits the remaining possible input orders. For n distinct keys, the tree must distinguish at least n factorial different orders.

A binary tree with height h has at most 2^h leaves. It follows that the height grows at least logarithmically in n! which corresponds asymptotically to n log n. The statement concerns general sorters that derive information solely from comparisons.

Difficulty levels

1. Interpret comparisons as branches of a decision tree.
2. Connect the number of leaves to the number of possible permutations.
3. Explain why Counting Sort does not fall under the same condition.

Pitfalls

The bound says nothing about whether every specific input requires the same number of comparisons. It applies to the worst case of the model and can be circumvented by additional structure of the keys.