基于比较的排序算法的复杂度下界是 $\Omega(n \log n)$，对于学过算法的人来说，这是一个基本常识。但它是怎么来的呢？
让未知世界无机可乘
在讨论排序之前，这里引入一个小游戏，为后续分析做一些准备。
这个游戏很简单。具体来说，我从整数范围 $[a, b)$ 当中（其中 $ b > a $）选择一个数字，由你来猜。你可以通过提问的方式，缩小答案范围。但这些问题的答案只能是「是」或者「否」，并且我保证会如实作答。现在的问题是，何种策略能够在所有情况下，尽可能快地猜到正确答案？
这个问题对稍有 CS 基础的读者来说应该是仅凭直感就能回答的：二分搜索呗。具体来说，先提问目标数字是不是位于 $\bigl[a, \lceil\frac{a + b}{2}\rceil\bigr)$ 之间，然后根据答案继续提问下去，直到得到正确答案。显然，它的时间复杂度是 $\Theta\bigl(\log_2 (b - a)\bigr)$。
那么问题来了。为什么这样的策略在平均情况下是最优的？换句话说，它为什么这样快呢？
为了说明这个问题，我们需要换一个角度去思考这个游戏。考虑到区间 $[a, b)$ 当中一共有 $ b - a $ 个整数。因此，「确定随机选择的数字为 $c$」这个命题所携带的信息量应当是 $-\log_2 \frac{1}{b - a}$。在游戏中，每次猜测 + 回答，事实上构成了一个命题。若根据这一系列的命题能够确定随机选择的数字，则这一系列命题所携带的信息量之和应该超过 $-\log_2 \frac{1}{b - a}$。那么，要尽可能快地找到这个数字，本质上就是要系列命题中的每一个都尽可能携带多的信息量，并且相互不重叠。
顺着这个思路往下想。由于游戏中规定了猜测的答案只能是「是」或「否」。我们定义答案为「是」的概率为 $p$，相应答案为「否」的概率为 $ 1 - p$。那么这个猜测 + 答案形成的命题所携带的信息量为 $-p\log_2 p - (1 - p)\log_2(1 - p)$。显然，要使得该命题所携带的信息量最大，就要让 $p = \frac{1}{2}$。这就是为什么二分搜索快的原因了。
这里从信息论的角度，用了一些公式去阐述问题。换成通俗的语言来描述，就是用二分搜索的策略，能够让每一次猜测都排除一半的可能性，并且无论如何都能排除一半的可能性。换而言之，二分搜索的策略，让未知世界无机可乘。
排序问题的重述
首先这里需要重新表述一下排序问题。
排序问题的本质可以理解为在 $n$ 个（不同）数的 $n!$ 种全排列中，选出一种，使其满足某种偏序关系（一般是小于或大于）。
现在我们考虑，基于元素比较的排序方法，每一次判定 $ a < b $，都相当于回答了一次「是否问题」。按照已有的知识，若要尽可能快地完成排序，就要让每一次大小判断的结果落在两种答案之一的概率接近；若不然，则这次比较带来的信息量较小，也就需要更多次的比较来完成排序。那么，基于比较的方法，至少需要多少次比较才能完成排序呢？换而言之，基于比较的排序算法，其复杂度下界是什么呢？
基于比较的排序算法的复杂度下界
现在我们已知，有 $n!$ 种可能的不同排列方式。假设我们有一个完美的算法，能够每次去除剩余可能性中的一半，则我们需要 $\log_2 n!$ 次比较。这就是基于比较的排序算法的复杂度下界：$\Omega (\log n!)$。
现在我们把它变换成比较好看的形式。考虑斯特灵级数
$$ n! = \sqrt{2\pi n}\Bigl(\frac{n}{\mathrm{e}}\Bigr)^{n}\Bigl(1 + \frac{1}{12n} + \frac{1}{288n^2} + \cdots\Bigr), $$
这也就是说
$$ \ln n! = n\ln n - n +\frac{1}{2}\ln(2\pi n) + \frac{1}{12n} - \frac{1}{360n^3} + \cdots. $$
因此，在渐进的意义下，$\log n! = \Theta (n\log n)$。这说明，基于比较的排序算法的复杂度下界是 $\Omega (n\log n)$。
