Standard Solution.

比较排序的时间复杂度下界为 $O(n \log n)$，证明如下：

设有 $n$ 个元素（不妨设它们构成 $1 \sim n$ 的一个排列）需要排序。

很明显，输入的 $n$ 个元素的排列顺序有 $n!$ 种可能。

设一共比较了 $k$ 次，则我们可以把 $n!$ 种可能分为 $2^k$ 类，时间复杂度为 $O(k)$。

为了完成比较排序，我们需要把每种可能都区分开，即 $2^k \ge n!$。

上述不等式解得 $k \ge O(n \log n)$，故比较排序的最低复杂度为 $O(n \log n)$。