On Sorting Complexity
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.