It's well known that the lower bound for the sorting problem (in the general case) is $\Omega(n \log n)$. The proof I was taught is somewhat involved and is based on paths in "decision" trees. Recently I've discovered an information-theoretic approach (or reformulation) to that proof.

First, let's state the problem: given a set of some objects with an ordering produce elements of that set in that order. For now it's completely irrelevant what these objects are, so we can assume them to be just numbers from 1 to n, or some permutation. Thus we'll be interested in sorting permutations.

We're given an ordering via a comparison function. It tells us if one object precedes (or is smaller than) another outputting True or False. Thus each invocation of the comparator gives us 1 bit of information.

The next question is how many bits we need to represent any permutation. It's just the binary logarithm of the number of all possible permutations of $n$ elements: $\log_2 n!$. Then we notice that

$$ \log_2 n! = \sum_{k=1}^n \log_2 k \ge \sum_{k=n/2}^{n} \log_2 k \ge \frac{n}{2} \log_2 \frac{n}{2} $$

$$ \log_2 n! = \sum_{k=1}^n \log_2 k \le n \log_2 n $$

(Or just use Stirling's approximation formula). Hence $\log_2 n! = \Theta(n \log n)$.

So what, you may ask. The key point of the proof is that sorting is essentially a search for a correct permutation of the input one. Since one needs $\log_2 n!$ bits to represent any permutation, we need to get that many bits of information somehow. Now let's get back to our comparison function. As we've figured out already it's able to give us only one bit of information per invocation. That implies that we need to call it $\log n! = \Theta(n \log n)$ times. And that's exactly the lower-bound for sorting complexity. Q.E.D.

Non-$n \log n$ sorting algorithms like RadixSort are possible because they use many more bits of information, taking advantage of numbers' structure.