算法（15）：sorting complexity-6.3
这一节的名字叫“排序复杂度（Sorting Complexity）”，但它实际上在回答一个更根本的问题：“只靠比较大小来排序，最快能有多快？有没有可能比归并排序更快？”
结论归并排序在“比较次数”上已经是最优的，但为了理解为什么，我们需要把“算法运行时间”和“物理极限”分开看。
1. 三组核心定义（先锁死术语）
计算模型（Model of Computation）：允许算法执行哪些操作。在排序问题中，我们限定为基于比较（Compare-based）的模型——你只能通过
a < b来获取两个元素相对顺序的信息，不能直接读取元素的内存地址来推算它的大小（比如不能像基数排序那样按位拆数字）。上界（Upper Bound）：某个已知算法在最坏情况下需要的操作次数。例如，归并排序能保证最多
~ N log₂ N次比较，所以“排序问题的上界是N log₂ N”。下界（Lower Bound）：任何算法（包括还没被发明出来的）在最坏情况下都不可能少于这个次数。它是对问题本身难度的证明。
如果上界 == 下界（在常数因子范围内），这个算法就是这个问题在对应成本模型下的最优算法（Optimal Algorithm）。
2. 为什么比较排序的下界是
~ N log₂ N？想象你对
N个互不相同的元素进行排序。你只能靠比较a[i]和a[j]来判断它们的顺序。物理事实：
输入有
N!种可能的排列（例如 3 个元素有 6 种排列，4 个元素有 24 种）。每一次比较，最多只能产生两种结果（
小于或大于等于）。因此，每次比较最多只能把“可能的排列数量”分成两半。
为了区分出
N!种不同的排列，你至少需要做log₂(N!)次比较。根据斯特林公式（Stirling's formula），
log₂(N!) ≈ N log₂ N。这意味着，任何基于比较的排序算法，在最坏情况下都不可能少于
N log₂ N次比较。（比较次数必然大于Nlog2N，以最坏情况为标准，否则比较无意义。避免一次就比出来的情况）
3. 结合归并排序看这张图
你已经知道归并排序的最坏情况比较次数就是
~ N log₂ N。现在把这个结论和刚学的下界合在一起看：
下界证明说：“无论你怎么设计，都不可能少于
N log₂ N次比较。”归并排序说：“我能做到
N log₂ N次比较。”所以，在“比较次数”这个成本模型下，归并排序已经是最优的，不可能再被超越了。这就是为什么 PPT 会说
Optimal algorithm = mergesort。4. 这个“最优”的局限性
“最优”只适用于比较次数，不是“所有资源”。
归并排序的空间成本：它需要额外的
aux数组（N个额外空间），所以它不是“空间最优”。存在原地排序算法（如堆排序），但它们的常数因子通常比归并排序大。如果允许不同操作模型：如果你不是只靠比较，而是利用键的物理表示（比如知道输入是 32 位整数），你可以使用基数排序（Radix Sort），它在某些情况下能达到
O(N)时间，突破N log N的限制。但这是因为你换了计算模型，而不是解决了比较排序的极限。5. 对你目前学习的意义
这一节的作用是告诉你：当你在归并排序和快速排序之间选择时，你不再需要担心“有没有可能发明一个比归并排序更快的基于比较的通用排序算法”——因为数学上已经证明了不存在。你能优化的只有常数因子、内存使用和缓存行为。
现在你已经知道了归并排序的理论天花板在哪里，下一节快速排序出现时，你就能直接看到它在实践层面（缓存、原地性）如何与理论最优的归并排序形成对比。如果你准备好进入快速排序（Quicksort），可以继续推进。