归并排序 图解题解
这道题到底在问什么
- 输入
- [5,2,8,1,9,3,7,4]
- 输出
- [1,2,3,4,5,7,8,9]
最优解：一步一步想明白
- 3对半切谁都会，取中点就行。归并真正的动作在“合”：两段已经各自有序，要并成一个有序段。因为两段已有序，用双指针扫一遍就能并完，不用重新排。
- 4左段指针、右段指针各指向自己当前最小的没取的数。比两个头，小的先放进结果、对应指针前进；一段取完，另一段剩下的直接接上。和合并两条有序链表一模一样。
- 5merge [0,1]第 1 趟开始 · 先把相邻单个两两合并。聚焦下标 0-1 的 [5,2]，单个元素天然有序，现在合它俩。
- 6i→5 j→2比 5 和 2 · 取右头 2
- 7已并 1/2取 2 放入位置 0 · 本段结果 [2]
- 80…1 有序本段合并完成 · [2,5] 有序
- 9i→8 j→1比 8 和 1 · 取右头 1
- 10已并 1/2取 1 放入位置 2 · 本段结果 [1]
- 112…3 有序本段合并完成 · [1,8] 有序
- 12i→9 j→3比 9 和 3 · 取右头 3
- 13已并 1/2取 3 放入位置 4 · 本段结果 [3]
- 144…5 有序本段合并完成 · [3,9] 有序
- 15i→7 j→4比 7 和 4 · 取右头 4
- 16已并 1/2取 4 放入位置 6 · 本段结果 [4]
- 176…7 有序本段合并完成 · [4,7] 有序
- 184 段二元有序第 1 趟结束 · 得到 4 个二元有序段：[2,5] [1,8] [3,9] [4,7]。下一趟把相邻两个二元段合成四元段。
- 19i→2 j→1比 2 和 1 · 取右头 1
- 20已并 1/4取 1 放入位置 0 · 本段结果 [1]
- 21i→2 j→8比 2 和 8 · 取左头 2
- 22已并 2/4取 2 放入位置 1 · 本段结果 [1,2]
- 23i→5 j→8比 5 和 8 · 取左头 5
- 24已并 3/4取 5 放入位置 2 · 本段结果 [1,2,5]
- 250…3 有序本段合并完成 · [1,2,5,8] 有序
- 26i→3 j→4比 3 和 4 · 取左头 3
- 27已并 1/4取 3 放入位置 4 · 本段结果 [3]
- 28i→9 j→4比 9 和 4 · 取右头 4
- 29已并 2/4取 4 放入位置 5 · 本段结果 [3,4]
- 30i→9 j→7比 9 和 7 · 取右头 7
- 31已并 3/4取 7 放入位置 6 · 本段结果 [3,4,7]
- 324…7 有序本段合并完成 · [3,4,7,9] 有序
- 332 段四元有序第 2 趟结束 · 得到 2 个四元有序段：[1,2,5,8] 和 [3,4,7,9]。最后一趟把它俩合成全有序。
- 34i→1 j→3比 1 和 3 · 取左头 1
- 35已并 1/8取 1 放入位置 0 · 本段结果 [1]
- 36i→2 j→3比 2 和 3 · 取左头 2
- 37已并 2/8取 2 放入位置 1 · 本段结果 [1,2]
- 38i→5 j→3比 5 和 3 · 取右头 3
- 39已并 3/8取 3 放入位置 2 · 本段结果 [1,2,3]
- 40i→5 j→4比 5 和 4 · 取右头 4
- 41已并 4/8取 4 放入位置 3 · 本段结果 [1,2,3,4]
- 42i→5 j→7比 5 和 7 · 取左头 5
- 43已并 5/8取 5 放入位置 4 · 本段结果 [1,2,3,4,5]
- 44i→8 j→7比 8 和 7 · 取右头 7
- 45已并 6/8取 7 放入位置 5 · 本段结果 [1,2,3,4,5,7]
- 46i→8 j→9比 8 和 9 · 取左头 8
- 47已并 7/8取 8 放入位置 6 · 本段结果 [1,2,3,4,5,7,8]
- 480…7 有序本段合并完成 · [1,2,3,4,5,7,8,9] 有序
- 49全有序全部合并完成 · 整个数组 [1,2,3,4,5,7,8,9] 从小到大有序。这就是归并排序：分到底，再一层层合上来。
⚠️ 容易写错的地方
✗ 错：while 结束后忘了接 L[i:] + R[j:]
✓ 对：主循环后必须把没取完那段的剩余补上
主循环在任一段取空时就停，另一段必然还剩更大的元素，漏接就丢数据
✗ 错：相等时写 L[i] < R[j] 把相等的取了右段
✓ 对：用 L[i] <= R[j]，相等取左
相等取左才稳定；左段元素原本靠前，相对顺序不能被打乱
✗ 错：以为分的过程在排序
✓ 对：排序只发生在“合”，分只是不停取中点切开
看清楚：单个元素时才开始合并，真正的比较和归位都在合并步里
完整代码（Python / C++ / Java）
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:] # 接上剩余残段C++
vector<int> merge_sort(vector<int>& a) {
if (a.size() <= 1) return a;
int mid = a.size() / 2;
vector<int> L(a.begin(), a.begin() + mid);
vector<int> R(a.begin() + mid, a.end());
L = merge_sort(L); R = merge_sort(R);
vector<int> res; int i = 0, j = 0;
while (i < L.size() && j < R.size()) {
if (L[i] <= R[j]) res.push_back(L[i++]);
else res.push_back(R[j++]);
}
res.insert(res.end(), L.begin()+i, L.end());
res.insert(res.end(), R.begin()+j, R.end());
return res;
}Java
List<Integer> mergeSort(List<Integer> a) {
if (a.size() <= 1) return a;
int mid = a.size() / 2;
List<Integer> L = mergeSort(new ArrayList<>(a.subList(0, mid)));
List<Integer> R = mergeSort(new ArrayList<>(a.subList(mid, a.size())));
List<Integer> res = new ArrayList<>();
int i = 0, j = 0;
while (i < L.size() && j < R.size())
res.add(L.get(i) <= R.get(j) ? L.get(i++) : R.get(j++));
res.addAll(L.subList(i, L.size()));
res.addAll(R.subList(j, R.size()));
return res;
}复杂度
时间复杂度
O(n log n)
log n 趟合并，每趟把 n 个元素各扫一次，与输入顺序无关
空间复杂度
O(n)
合并需要一个等长的临时数组装结果
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 归并排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
归并排序为什么是稳定的？+
合并时相等的元素优先取左段（L[i] <= R[j]）。左段元素原本就排在右段前面，这样相等元素的相对顺序不变，所以稳定。
它和快速排序怎么选？+
归并稳定、最坏也是 O(n log n)，但要 O(n) 额外空间；快排原地（O(log n) 栈），平均更快但最坏 O(n²)。要稳定或要最坏保证选归并，要省空间且数据随机选快排。
“合并两个有序”这个子过程还能用在哪？+
合并 K 个有序链表、求逆序对（取右段元素时左段剩余个数就是新增逆序对）、外部排序归并多个有序文件。它是分治里很通用的积木。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 归并排序 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。