归并排序的原理是什么？为什么它稳定且最坏也是 O(n log n)？

简化版

归并排序是分治:把数组从中间一分为二,递归地把左右两半各自排好,再合并(merge) 两个有序数组成一个有序数组。合并时按顺序挑两边较小的,所以任何情况都是 O(n log n)(每层合并 O(n)、共 log n 层),且稳定(相等时优先取左边)。代价是需要 O(n) 辅助空间存合并结果。适合要求稳定、链表排序、外部排序的场景。

详细版

void mergeSort(int[] a, int lo, int hi, int[] tmp) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid, tmp);        // 排左半
    mergeSort(a, mid + 1, hi, tmp);    // 排右半
    merge(a, lo, mid, hi, tmp);        // 合并两个有序半
}
void merge(int[] a, int lo, int mid, int hi, int[] tmp) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= 保证稳定：相等取左边
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (int x = lo; x <= hi; x++) a[x] = tmp[x];    // 拷回原数组
}

分:递归对半拆到单个元素(天然有序)。
治+并:合并两个有序子数组——用双指针,每次取较小的放进结果。
a[i] <= a[j] 用 <=:相等时优先取左边的,保证稳定。

完整版教学

一、核心思想:分而治之,难点在合并

归并排序的思路很清晰:一个大问题拆成两个小问题,小问题解决了再合起来。

分(Divide):把数组从中点切成左右两半,一直递归切到每段只剩 1 个元素(单个元素天然有序)。
治(Conquer):递归排序左右两半。
并(Merge):把两个已经有序的半合并成一个有序的整体。

和快排「在划分时干活」不同,归并的活儿全在合并这一步。理解归并的关键是理解「如何 O(n) 合并两个有序数组」。

二、合并两个有序数组:双指针

合并是归并的精髓。给两个有序数组,要合成一个有序数组:用两个指针 i、j 分别指向两个数组的开头,每次比较两个指针指向的元素,把较小的放进结果、该指针后移;一个数组走完了,把另一个剩下的直接接上。因为两边本来就有序,这样一趟 O(n) 扫描就能合并出有序结果。

合并 [1,4,7] 和 [2,3,8]:
i→1, j→2: 1<2 取1     → [1]
i→4, j→2: 2<4 取2     → [1,2]
i→4, j→3: 3<4 取3     → [1,2,3]
i→4, j→8: 4<8 取4     → [1,2,3,4]
i→7, j→8: 7<8 取7     → [1,2,3,4,7]
左边走完,接上右边剩下的8 → [1,2,3,4,7,8]

三、为什么最坏也是 O(n log n)（重点）

这是归并相对快排的最大优势——性能非常稳定,没有最坏退化。原因:

拆分总是严格对半,所以递归树永远是 log n 层(和数据内容无关,不像快排会因基准选得差而失衡)。
每一层的所有合并加起来,总共处理 n 个元素,是 O(n)。
层数 × 每层 = O(n log n),且最好、平均、最坏都一样。

快排的层数会因基准而波动(最坏 n 层),归并的层数恒为 log n,所以归并没有 O(n²) 的最坏情况。代价是它需要辅助空间。

四、为什么归并稳定

归并排序稳定,关键在合并时的比较用 a[i] <= a[j](小于等于):当左右两边元素相等时,优先取左边的。因为左边的元素在原数组里本来就排在前面,优先取它就保持了相等元素的原有相对顺序。

如果写成 a[i] < a[j](相等时取右边),就会破坏稳定性。所以「相等取左」是归并保持稳定的核心细节。

五、空间复杂度:O(n) 是它的短板

归并排序需要一个和原数组一样大的辅助数组来存合并结果,所以空间是 O(n)(加上递归栈 O(log n))。这是它相对快排(原地 O(log n))、堆排(原地 O(1))的劣势——数据量极大、内存紧张时不划算。有「原地归并」的做法,但实现复杂、常数大,一般不用。

六、归并的独特优势:链表与外部排序

尽管费空间,归并在两个场景里无可替代:

链表排序:链表不能随机访问,快排/堆排不好用,但归并只需要「找中点 + 合并」,而链表合并不需要额外数组(改指针即可),所以链表归并空间 O(1)、是链表排序的最佳选择。
外部排序:数据大到内存放不下(如几百 GB 的文件),归并的「分块排序 + 多路合并」是标准方案——每次只需在内存里合并几路有序数据。
要求稳定:需要稳定排序时,归并是 O(n log n) 里的首选(Java 对象排序的 TimSort 就是归并的改进)。

七、复杂度与特点小结

时间:最好=平均=最坏都是 O(n log n)(拆分恒对半)。
空间 O(n):辅助数组(数组版);链表版可 O(1)。
稳定:合并时相等取左。
优点:性能稳定无退化、稳定排序、适合链表/外部排序。
缺点:费 O(n) 空间、常数比快排大(实际略慢于快排)。

八、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：左右子段已有序，输出区已写部分始终是两侧已消费元素的有序合并。

对应的状态推进是：比较两侧指针，相等时先取左侧，复制完一侧后追加另一侧。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。T(n)=2T(n/2)+Θ(n)=Θ(n log n)，数组辅助空间 O(n)。

带数字走一遍：[2a,4] 与 [2b,3] 合并时先取 2a，稳定地得到 [2a,2b,3,4]。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	要求稳定、最坏复杂度保证、链表排序或外部排序时很合适
时间复杂度	最好/平均/最坏 Θ(n log n)
额外空间	数组 O(n)，递归栈 O(log n)
关键边界	中点和闭区间要配套；相等时先取右侧会失去稳定性
替代方案	内存敏感的数组排序可考虑快排或堆排

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

九、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“要求稳定、最坏复杂度保证、链表排序或外部排序时很合适”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写最好/平均/最坏 Θ(n log n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“T(n)=2T(n/2)+Θ(n)=Θ(n log n)，数组辅助空间 O(n)”。
误区：重复值和边界值不会改变代码。 中点和闭区间要配套；相等时先取右侧会失去稳定性。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“左右子段已有序，输出区已写部分始终是两侧已消费元素的有序合并”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[2a,4] 与 [2b,3] 合并时先取 2a，稳定地得到 [2a,2b,3,4]”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“内存敏感的数组排序可考虑快排或堆排”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

十、加强记忆

归并排序 = 分治:从中点对半拆到单元素,再合并两个有序半(双指针每次取较小的,<= 相等取左保证稳定)。最好=平均=最坏都是 O(n log n)(拆分恒对半、层数固定 log n,无退化),这是它比快排稳的地方;代价是 O(n) 辅助空间。独特优势:链表排序(O(1) 空间)、外部排序、要稳定时的首选。

简化版

详细版