option 3

Any decision tree that sorts n elements has height Omega(n lg n).

Proof:

A binary tree of height h has <= 2^h leaves.

At least n! leaves are required for sorting.

Thus n! <= 2^h.

h >= lg(n!) = sum_{i=2}^n lg(i) > sum_{i=n/2}^n lg(i) > sum_{i=n/2}^n lg(n/2)

> (n/2) lg(n/2) = Omega(n lg n).