Well. You know that maximum number of leaves in binary tree with height *x* is *2^x*. And your decision tree must have at least *n!* leaves so *n! <= 2^x*.

From that you have inequality *log n! <= x* (I will omit the *2* in logarithm. Firtsly it’s nicer, secodly it doesn’t matter).

Now we need two estimations for value of *n!*. First, we know, that *n^n >= n!*, that’s easy to see, because we have product of *n* numbers and all are bigger than *n*. Also we know, that *n! >= (n/2)^(n/2)*. If you write first *n/2* elements of *n!* they are all bigger than *n/2*, so inequality holds.

*n^n >= n! >= (n/2)^(n/2)*

But logarithm holds inequalities. So *log(n^n) >= log(n!) >= log((n/2)^(n/2))*. And because *log(a^b) = b.log(a)* then *n.log(n) >= log(n!) >= (n/2).log(n/2)*. But in O-notation both left and right side is *O(n.log(n))*. And because *log(n!)* is both bigger and smaller than *O(n.log(n))* it must be eqaul to it.

From that we know, that *O(log(n!)) = O(n.log(n))*. (And same from theta or omega). So every sort based on comparison must have time complexity at least *n.log(n)*.