Each comparison of objects provides one bit of information.
So k comparisons provide k bits of information, or 2^k possibilities.
Therefore to distinguish between n options, we need at least log_2(n) comparisons.
There are n! ways of ordering a list of length n.
log(n!) ~ n * log (n)
So to sort a list of length n, we need at least O(n * log(n)) comparisons.
> log(n!) ~ n * log (n)
Random aside: while this is usually proven with Stirling's approximation, there is a much simpler proof. For the upper bound, n! <= n^n because 1 <= n, ..., n <= n. For the lower bound, n! >= (n/2)^(n/2) because you can drop the first n/2 terms without increasing the product and estimate the last n/2 terms as being >= n/2. That gives the double inequality (n/2)^(n/2) <= n! <= n^n. Take logs and you get (n/2) log(n/2) <= log(n!) <= n log(n). What makes this proof tick is that while (n/2)^(n/2) is a really shitty lower bound on n!, the shittiness evaporates once you take logs.