The Bound

Since a binary tree of height h has no more than 2^h leaves, we have: $2^h \ge n! \ge (n/2)^{n/2}$. The latter inequality comes from breaking up the factorial function:

$$n! = (n)(n-1)\cdots(n/2)(n/2-1)\cdots (2)(1) \ge (n/2)(n/2)\cdots(n/2)(1)\dots(1)(1) = (n/2)^{n/2}.$$

Taking logs and using their monotonicity property, we have $h \ge \log((n/2)^{n/2}) = n/2 \log(n) - n/2 = \Omega(n\log n)$.

So, the height of the tree is at least $\Omega(n \log n)$... with any fewer comparisons, we won't be able to sort.