学习顺序主线第 15 / 22 课 · 阶段 5

为什么现在学:结合递归与双指针,体验先解决子问题、再合并结果。

返回算法课程
排序进阶

归并排序Merge Sort

先把两半各自排好,再用双指针线性合并。

45 分钟前置:数组 · 递归 · 双指针

学完这一课,你应该能做到

  • 画出拆分树与实际返回次序
  • 用两个头部的最小值完成合并
  • 按层求和解释 n log n,并说明稳定性

01先从一个问题出发

两叠已经排好序的卡片,如何高效合成一叠?

一个具体的例子

[4,1,3,2];先递归,再合并。

先回答一个更小的问题:两段有序数组怎么合并

面对 [1,4] 与 [2,3],全体最小值一定是两段头部中的较小者,因为各段其余元素都不小于自己的头部。取 1 后只移动左指针;再比较 4 与 2,取 2;再取 3;最后追加左侧剩下的 4。每个元素恰好输出一次。

于是困难只剩下『如何让两段有序』。把每段继续平分,直到长度为 0 或 1,可以直接视为有序;子调用返回后,再执行刚刚理解的合并。递归负责把前提变真,合并负责把结论扩大。

拆分并不等于排序已经发生

对 [4,1,3,2],拆成 [4,1]、[3,2] 时,两个片段仍无序。继续拆成单项,才得到最基础的有序片段。返回时合成 [1,4]、[2,3],最外层再合成 [1,2,3,4]。

本课使用半开区间 [left,right)。mid 将它准确分成 [left,mid) 和 [mid,right),无重叠也无遗漏。right−left≤1 才是终止判断;不能把 right 当作有效下标访问。

02最直接的办法,为什么慢?

反复找未排序区域中的最小值。

暴力 · O(n²)

每次选择都重新扫描剩余元素,累计平方级比较。

03一步步,推导出优化思路

1

先学会合并两段有序数据

两个有序数组可以只比较当前头部,用 O(n) 时间合并。

2

递归拆到天然有序的单项

把问题不断平分,单元素天然有序。

3

返回时逐层合并

自底向上合并;每一层总共处理 n 个元素,层数约 log₂ n。

贯穿算法的不变量

合并时,缓冲区已排序,且不大于两个输入区间中尚未取出的元素。

拿一个小输入,逐步手算

[4,1,3,2];先递归,再合并。

阶段两个输入区间选择 / 结果
拆分[4,1] 与 [3,2]还未有序,继续拆
左子问题返回[4] 与 [1]取 1,再取 4 → [1,4]
右子问题返回[3] 与 [2]取 2,再取 3 → [2,3]
顶层合并[1,4] 与 [2,3]比较 1、2,取 1
继续[4] 与 [2,3]依次取 2、3
一侧耗尽[4] 与 []追加 4 → [1,2,3,4]

为什么可以整段追加剩余元素?它们内部已有序,另一段又已取空,不再有竞争者需要比较。

递归与合并分别证明

  1. 长度≤1 的区间有序,基础情形成立。假设两个更短区间已经被递归正确排序。
  2. 合并时,每次选择两个未取头部中的较小者,它就是所有剩余元素中的最小者;已输出部分始终有序。
  3. 所有元素被输出且没有丢失或重复,再写回原区间,因此父问题有序。对区间长度归纳,最外层也有序。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Merge Sort交互演示
STEP 01 / 18
4
0
1
1
3
2
2
3
当前处理已处理 / 已确定未处理
01

从左到右观察数组。橙色表示当前比较,绿色表示已确定的位置。

merge_sort.py参考实现 · 当前第 2 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

sort(left, mid)
先把左半段完整排好,返回后才开始右半段。递归树画在同一层,不代表代码并行执行。
if a[i] <= a[j]:
相等时取左段,原先较早的元素仍先输出,保证稳定性。
merged.extend(a[i:mid])
循环结束后补上左边剩余项;右边也做同样处理,其中至少一段为空。
a[left + offset] = value
把临时合并结果写回当前区间。这个偏移是相对于 left,不能总是从数组下标 0 覆盖。

05复杂度,来自具体的工作量

时间复杂度
O(nlog⁡n)O(n\log n)

递推 T(n)=2T(n/2)+O(n),共有 O(log n) 层,每层 O(n),最好和最坏均为 O(n log n)。

辅助空间
O(n)O(n)

合并缓冲区峰值 O(n),递归栈 O(log n),合计 O(n)。

拖动 n,看看增长速度

把工作量具体数出来

n=8 时,最底层合并 4 组长度 2,总处理 8 项;上层 2 组长度 4 仍共 8 项;最上层处理 8 项。合并工作约 8×3。

一般有 O(log n) 层,每层合并区间总长度 O(n),因此 O(n log n)。n 不是 2 的幂时两半略不等长,增长阶不变。

临时合并数组峰值 O(n),递归栈 O(log n),合计 O(n)。累计分配量可能大于峰值空间,分析空间复杂度通常关注同时存活的数据。

06看到什么,应该想到它?

这些特征值得停下来想一想:

关键词只是线索,继续检查适用条件

07这些细节,容易踩坑

01

相等时先选左边

使用 <= 保证跨区间的同值元素仍稳定。

02

半开区间

本实现处理 [left, right),不要把 right 当作有效下标。

用反例检查前提

把不相邻的两个问题混成同一个区间

若左递归也包含 mid、右递归也从 mid 开始,mid 被重复处理;长度为 2 时还可能让一个子问题与父问题一样大,无法结束。

怎样修正:固定半开约定,左右区间分别 [left,mid)、[mid,right)。手算长度 0、1、2 与奇数长度,检查每次都严格变小。

08把想法带进真实题目

合上答案,自己推一次

有相等元素时选谁

合并 [1A,3] 与 [1B,2],A 原先在 B 左边。写出稳定的输出顺序,并说明相等时选右边会怎样。

需要一点提示

第一次比较就是稳定性决策。

查看完整推导与答案
  1. 先取 1A,再取 1B,然后 2、3,得到 [1A,1B,2,3]。
  2. 若第一次取右边的 1B,结果数值仍有序,但 A、B 的相对顺序被改变。
  3. 排序正确性与稳定性是两件事,稳定性需要额外检查相等时的处理。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01为什么每层合并是 O(n)?

02相等时先选哪个?

03常规数组归并的额外空间?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。