It's well known that lower bound for sorting problem (in general case) is
. 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.