题目描述
分：对半切到只剩单个元素（天然有序）。合：把相邻的两个有序段合并成更大的有序段，直到合成整个数组。
思路解析
对半切谁都会（直接取中点）。归并的真正动作在"合"：两个已经各自有序的段，要合成一个有序段。如果每次都重新排会很慢，但因为两段已有序，用双指针一遍就能并完。
左段指针 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 个有序链表。
参考代码（Python）
1def merge_sort(a):
2 if len(a) <= 1: return a # 单个天然有序
3 mid = len(a) // 2
4 L = merge_sort(a[:mid]) # 分 + 递归排左
5 R = merge_sort(a[mid:]) # 分 + 递归排右
6 res, i, j = [], 0, 0
7 while i < len(L) and j < len(R): # 合并：谁小取谁
8 if L[i] <= R[j]: res.append(L[i]); i += 1
9 else: res.append(R[j]); j += 1
10 return res + L[i:] + R[j:] # 接上剩余残段复杂度分析
- 时间复杂度：O(n log n) —— log n 层划分，每层合并总共扫 n 个元素，与输入顺序无关
- 空间复杂度：O(n) —— 合并需要一个等长的临时数组装结果
套路模板
记住骨架：双指针谁小取谁、相等取左保稳定、最后接残段。这个"合并有序"是归并排序、求逆序对、合并 K 个有序的共同内核。
1i = j = 0; res = []
2while i < len(L) and j < len(R):
3 if L[i] <= R[j]: res.append(L[i]); i += 1 # 等时取左=稳定
4 else: res.append(R[j]); j += 1
5res += L[i:] + R[j:] # 接残段，一段空了补另一段易错点
- 错误写法：while 结束后忘了 res + L[i:] + R[j:] → 正确写法：主循环后必须把没取完那段的剩余补上（主循环在任一段取空时就停，另一段必然还剩若干个更大的元素，漏接就丢数据）
- 错误写法：相等时写 L[i] < R[j] 取右 → 正确写法：L[i] <= R[j] 相等取左（相等取左才稳定，左段元素原本靠前，相对顺序不能被打乱）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。