§1

题目描述

分：对半切到只剩单个元素（单个天然有序）。合：把相邻的两个有序段合并成更大的有序段，一层层合到整个数组。

输入 = [5,2,8,1,9,3,7,4]

输出 = [1,2,3,4,5,7,8,9]

§2

思路解析动画文字版

对半切谁都会，取中点就行。归并真正的动作在“合”：两段已经各自有序，要并成一个有序段。因为两段已有序，用双指针扫一遍就能并完，不用重新排。

左段指针、右段指针各指向自己当前最小的没取的数。比两个头，小的先放进结果、对应指针前进；一段取完，另一段剩下的直接接上。和合并两条有序链表一模一样。

第 1 趟 · 宽度 1→2：第 1 趟开始 · 先把相邻单个两两合并。聚焦下标 0-1 的 [5,2]，单个元素天然有序，现在合它俩。

第 1 趟 · 合 [5][2]：比 5 和 2 · 取右头 2

第 1 趟 · 合 [5][2]：取 2 放入位置 0 · 本段结果 [2]

第 1 趟 · 合 [5][2]：本段合并完成 · [2,5] 有序

第 1 趟 · 合 [8][1]：比 8 和 1 · 取右头 1

第 1 趟 · 合 [8][1]：取 1 放入位置 2 · 本段结果 [1]

第 1 趟 · 合 [8][1]：本段合并完成 · [1,8] 有序

第 1 趟 · 合 [9][3]：比 9 和 3 · 取右头 3

第 1 趟 · 合 [9][3]：取 3 放入位置 4 · 本段结果 [3]

第 1 趟 · 合 [9][3]：本段合并完成 · [3,9] 有序

第 1 趟 · 合 [7][4]：比 7 和 4 · 取右头 4

第 1 趟 · 合 [7][4]：取 4 放入位置 6 · 本段结果 [4]

第 1 趟 · 合 [7][4]：本段合并完成 · [4,7] 有序

第 1 趟完成：第 1 趟结束 · 得到 4 个二元有序段：[2,5] [1,8] [3,9] [4,7]。下一趟把相邻两个二元段合成四元段。

第 2 趟 · 合 [2,5]+[1,8]：比 2 和 1 · 取右头 1

第 2 趟 · 合 [2,5]+[1,8]：取 1 放入位置 0 · 本段结果 [1]

第 2 趟 · 合 [2,5]+[1,8]：比 2 和 8 · 取左头 2

第 2 趟 · 合 [2,5]+[1,8]：取 2 放入位置 1 · 本段结果 [1,2]

第 2 趟 · 合 [2,5]+[1,8]：比 5 和 8 · 取左头 5

第 2 趟 · 合 [2,5]+[1,8]：取 5 放入位置 2 · 本段结果 [1,2,5]

第 2 趟 · 合 [2,5]+[1,8]：本段合并完成 · [1,2,5,8] 有序

第 2 趟 · 合 [3,9]+[4,7]：比 3 和 4 · 取左头 3

第 2 趟 · 合 [3,9]+[4,7]：取 3 放入位置 4 · 本段结果 [3]

第 2 趟 · 合 [3,9]+[4,7]：比 9 和 4 · 取右头 4

第 2 趟 · 合 [3,9]+[4,7]：取 4 放入位置 5 · 本段结果 [3,4]

第 2 趟 · 合 [3,9]+[4,7]：比 9 和 7 · 取右头 7

第 2 趟 · 合 [3,9]+[4,7]：取 7 放入位置 6 · 本段结果 [3,4,7]

第 2 趟 · 合 [3,9]+[4,7]：本段合并完成 · [3,4,7,9] 有序

第 2 趟完成：第 2 趟结束 · 得到 2 个四元有序段：[1,2,5,8] 和 [3,4,7,9]。最后一趟把它俩合成全有序。

第 3 趟 · 合两个四元段：比 1 和 3 · 取左头 1

第 3 趟 · 合两个四元段：取 1 放入位置 0 · 本段结果 [1]

第 3 趟 · 合两个四元段：比 2 和 3 · 取左头 2

第 3 趟 · 合两个四元段：取 2 放入位置 1 · 本段结果 [1,2]

第 3 趟 · 合两个四元段：比 5 和 3 · 取右头 3

第 3 趟 · 合两个四元段：取 3 放入位置 2 · 本段结果 [1,2,3]

第 3 趟 · 合两个四元段：比 5 和 4 · 取右头 4

第 3 趟 · 合两个四元段：取 4 放入位置 3 · 本段结果 [1,2,3,4]

第 3 趟 · 合两个四元段：比 5 和 7 · 取左头 5

第 3 趟 · 合两个四元段：取 5 放入位置 4 · 本段结果 [1,2,3,4,5]

第 3 趟 · 合两个四元段：比 8 和 7 · 取右头 7

第 3 趟 · 合两个四元段：取 7 放入位置 5 · 本段结果 [1,2,3,4,5,7]

第 3 趟 · 合两个四元段：比 8 和 9 · 取左头 8

第 3 趟 · 合两个四元段：取 8 放入位置 6 · 本段结果 [1,2,3,4,5,7,8]

第 3 趟 · 合两个四元段：本段合并完成 · [1,2,3,4,5,7,8,9] 有序

排序完成：全部合并完成 · 整个数组 [1,2,3,4,5,7,8,9] 从小到大有序。这就是归并排序：分到底，再一层层合上来。

三个高频追问：稳定性来源、和快排的取舍、合并有序这个内核的复用场景。

§3

参考代码

def merge_sort(a):    if len(a) <= 1: return a            # 单个天然有序    mid = len(a) // 2    L = merge_sort(a[:mid])            # 分 + 递归排左    R = merge_sort(a[mid:])           # 分 + 递归排右    res, i, j = [], 0, 0    while i < len(L) and j < len(R):   # 合并：谁小取谁        if L[i] <= R[j]: res.append(L[i]); i += 1        else: res.append(R[j]); j += 1    return res + L[i:] + R[j:]         # 接上剩余残段

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间复杂度：O(n log n)，log n 趟合并，每趟把 n 个元素各扫一次，与输入顺序无关
空间复杂度：O(n)，合并需要一个等长的临时数组装结果

§5

易错点

✗ 错误写法：while 结束后忘了接 L[i:] + R[j:]

✓ 正确写法：主循环后必须把没取完那段的剩余补上

主循环在任一段取空时就停，另一段必然还剩更大的元素，漏接就丢数据

✗ 错误写法：相等时写 L[i] < R[j] 把相等的取了右段

✓ 正确写法：用 L[i] <= R[j]，相等取左

相等取左才稳定；左段元素原本靠前，相对顺序不能被打乱

✗ 错误写法：以为分的过程在排序

✓ 正确写法：排序只发生在“合”，分只是不停取中点切开

看清楚：单个元素时才开始合并，真正的比较和归位都在合并步里

面试追问把动画讲成自己的话

追问归并排序为什么是稳定的？

合并时相等的元素优先取左段（L[i] <= R[j]）。左段元素原本就排在右段前面，这样相等元素的相对顺序不变，所以稳定。

追问它和快速排序怎么选？

归并稳定、最坏也是 O(n log n)，但要 O(n) 额外空间；快排原地（O(log n) 栈），平均更快但最坏 O(n²)。要稳定或要最坏保证选归并，要省空间且数据随机选快排。

追问“合并两个有序”这个子过程还能用在哪？

合并 K 个有序链表、求逆序对（取右段元素时左段剩余个数就是新增逆序对）、外部排序归并多个有序文件。它是分治里很通用的积木。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 排序套路 12/12

堆排序

困难 · 沿着排序套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

def merge_sort(a): if len(a) <= 1: return a # 单个天然有序 mid = len(a) // 2 L = merge_sort(a[:mid]) # 分 + 递归排左 R = merge_sort(a[mid:]) # 分 + 递归排右 res, i, j = [], 0, 0 while i < len(L) and j < len(R): # 合并：谁小取谁 if L[i] <= R[j]: res.append(L[i]); i += 1 else: res.append(R[j]); j += 1 return res + L[i:] + R[j:] # 接上剩余残段