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).