Quiz: Comparison Sort Theory

Why can't any comparison-based sort beat $O(n \log n)$ in the worst case?

1. A.Because there are $n!$ possible orderings and each comparison only eliminates half
2. B.Because the decision tree must have at least $n!$ leaves, requiring height $\geq \log(n!)$
3. C.Because computers can only compare two elements at a time
4. D.Because merge sort is already optimal and it takes $O(n \log n)$