题目描述
思路解析动画文字版
对半切谁都会（直接取中点）。归并的真正动作在"合"：两个已经各自有序的段，要合成一个有序段。如果每次都重新排会很慢，但因为两段已有序，用双指针一遍就能并完。
左段指针 i、右段指针 j 各指向当前最小未取的元素。比较两个头，小的放进结果、对应指针前进，直到一段取完，另一段剩余直接接上——和合并两个有序链表一模一样。
对半切分：从中点切开：左半 [3,1]（亮）、右半 [2,4]（暗）。两半各自再递归切分、排序，下面先盯住左半。
左半再切到单个：左半 [3,1] 继续对半切成单个的 [3] 和 [1]——单个元素天然有序，这就是递归的底，分到这里不能再分。
左半合并 · 比 3 和 1 取 1：左半 [3,1] 递归到底再合并，排成 [1,3]。右半 [2,4] 本就有序。现在两个有序段都备好，进入合并。
合并准备 · 两段亮起：左段指针 i 指下标 0（值 1），右段指针 j 指下标 2（值 2）。准备比较两个段的头，谁小取谁。
比 1 和 2 · 取左头 1：比左头 1 和右头 2：1 更小，取 1 放进结果。结果 [1]。左指针 i 前进到下标 1（值 3）。
比 3 和 2 · 这次取右头 2：比左头 3 和右头 2：这次右头更小，取右头 2（值 2 换到结果第 2 位，3 顺势后移）。这就是取右、左指针不动的分支。结果 [1,2]，右指针 j 前进。
比 3 和 4 · 取左头 3：比左头 3 和右头 4：3 更小，取 3。结果 [1,2,3]。左指针 i 前进，左段已取完。
左段空 · 右段剩余直接接上：左段取空后，不用再比较，把右段剩下的 4 整段接到结果末尾。合并完成，整个数组 [1,2,3,4] 有序——别漏了这步"接残段"。
归并是"分治"的标准范本：把大问题对半拆、解决子问题、再合并。"合并两个有序"这个子过程是它的核心积木，也直接用于求逆序对、合并 K 个有序链表。
参考代码
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:] # 接上剩余残段复杂度
- 时间复杂度：O(n log n)，log n 层划分，每层合并总共扫 n 个元素，与输入顺序无关
- 空间复杂度：O(n)，合并需要一个等长的临时数组装结果
可套用的代码模板
记住骨架：双指针谁小取谁、相等取左保稳定、最后接残段。这个"合并有序"是归并排序、求逆序对、合并 K 个有序的共同内核。
Python
i = j = 0; res = []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 += 1res += L[i:] + R[j:] # 接残段，一段空了补另一段易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
堆排序
困难 · 沿着 排序套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题