Lower bound for comparison-based sorting algorithms

This includes algorithms like Merge sort and Insertion sort.

Assume we’re given a correct sorting algorithm. It’s a black box to us, but we want to show to show that its runtime cannot be $o(n\log n)$.

Comparison based model: when talking about arrays and runtime, we access the input array $A[\mathrm{1..}n]$ via comparisons. For example, is $A[i]\ge A[j]$?

Decision tree: a rooted binary tree. Labels on nodes and edges. Nodes ask a question, and edges are outputs/answers. Labels on the edges have to be unique.

Use the decision tree to show that the worst case number of comparisons (aka one execution possibility) is $\Omega (n\lg n)$. In other words, the depth/height of the tree is $n\lg n$.

If the algorithm is correct, how many leaves must exist in the decision tree? The number of leaves must be $\ge n!$, where $|A|=n$. We’re permutating $A$ here.

Each leaf corresponds to a potential output of the algorithm, after it makes a decision. Therefore, there are $n!$ ways to place $n$ elements.

Since leaves $\le 2^h$, we have $(\frac{n}{2}{)}^{\frac{n}{2}}\ge n!$, and so the height $h\ge \frac{n}{2}\log \left(\frac{n}{2}\right)$.