中等排序 · 归并
归并排序 图解题解
这道题到底在问什么
分：对半切到只剩单个元素（天然有序）。合：把相邻的两个有序段合并成更大的有序段，直到合成整个数组。
- 输入
- [3, 1, 2, 4]
- 输出
- [1, 2, 3, 4]
最优解：一步一步想明白
- 3对半切谁都会（直接取中点）。归并的真正动作在"合"：两个已经各自有序的段，要合成一个有序段。如果每次都重新排会很慢，但因为两段已有序，用双指针一遍就能并完。
- 4左段指针 i、右段指针 j 各指向当前最小未取的元素。比较两个头，小的放进结果、对应指针前进，直到一段取完，另一段剩余直接接上——和合并两个有序链表一模一样。
- 5mid=2从中点切开：左半 [3,1]（亮）、右半 [2,4]（暗）。两半各自再递归切分、排序，下面先盯住左半。
- 6L → [3] [1]左半 [3,1] 继续对半切成单个的 [3] 和 [1]——单个元素天然有序，这就是递归的底，分到这里不能再分。
- 7L=[1,3]左半 [3,1] 递归到底再合并，排成 [1,3]。右半 [2,4] 本就有序。现在两个有序段都备好，进入合并。
- 8i=0 j=2左段指针 i 指下标 0（值 1），右段指针 j 指下标 2（值 2）。准备比较两个段的头，谁小取谁。
- 9取 L → res=[1]比左头 1 和右头 2：1 更小，取 1 放进结果。结果 [1]。左指针 i 前进到下标 1（值 3）。
- 10取 R → res=[1,2]比左头 3 和右头 2：这次右头更小，取右头 2（值 2 换到结果第 2 位，3 顺势后移）。这就是取右、左指针不动的分支。结果 [1,2]，右指针 j 前进。
- 11取 L → res=[1,2,3]比左头 3 和右头 4：3 更小，取 3。结果 [1,2,3]。左指针 i 前进，左段已取完。
- 12res=[1,2,3,4]左段取空后，不用再比较，把右段剩下的 4 整段接到结果末尾。合并完成，整个数组 [1,2,3,4] 有序——别漏了这步"接残段"。
- 15归并是"分治"的标准范本：把大问题对半拆、解决子问题、再合并。"合并两个有序"这个子过程是它的核心积木，也直接用于求逆序对、合并 K 个有序链表。
⚠️ 容易写错的地方
✗ 错：while 结束后忘了 res + L[i:] + R[j:]
✓ 对：主循环后必须把没取完那段的剩余补上
主循环在任一段取空时就停，另一段必然还剩若干个更大的元素，漏接就丢数据
✗ 错：相等时写 L[i] < R[j] 取右
✓ 对：L[i] <= R[j] 相等取左
相等取左才稳定，左段元素原本靠前，相对顺序不能被打乱
完整代码（Python）
Python
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:] # 接上剩余残段套路模板 · 归并的合并步（背下来）
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 += 1
res += L[i:] + R[j:] # 接残段，一段空了补另一段复杂度
时间复杂度
O(n log n)
log n 层划分，每层合并总共扫 n 个元素，与输入顺序无关
空间复杂度
O(n)
合并需要一个等长的临时数组装结果
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 归并排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「归并」，换最直接的暴力解会差在哪？+
归并抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。