一、核心流程：分治 + 合并
[3, 7, 8, 5, 2, 1, 9, 4]
↓ 分割
[3, 7, 8, 5] [2, 1, 9, 4]
↓ 分割 ↓ 分割
[3, 7] [8, 5] [2, 1] [9, 4]
↓ 分割 ↓ 分割
[3][7] [8][5] [2][1] [9][4]
↓ 合并 ↓ 合并
[3, 7] [5, 8] [1, 2] [4, 9]
↓ 合并 ↓ 合并
[3, 5, 7, 8] [1, 2, 4, 9]
↓ 合并
[1, 2, 3, 4, 5, 7, 8, 9]
二、自顶向下（递归）实现
merge 整体操作流程：
- 创建临时数组：大小为
right - left + 1用于存放合并结果。 - 双指针比较：
i指向左半区间[left, mid]，j指向右半区间[mid+1, right]。 - 取较小者：比较
nums[i]和nums[j]，将较小的放入临时数组，对应指针前进。 - 收尾：将左半或右半剩余的元素全部放入临时数组。
- 写回：将临时数组的内容复制回原数组的
[left, right]位置。
mergeSort 递归整体流程：
- 终止条件：
left >= right时返回。 - 分割：计算中点
mid，将数组分成两半。 - 递归左半：对
[left, mid]排序。 - 递归右半：对
[mid+1, right]排序。 - 合并：将两个有序子数组合并成一个有序数组。
void merge(vector<int>& nums, int left, int mid, int right) {
vector<int> temp(right - left + 1); // ① 临时数组
int i = left, j = mid + 1, k = 0; // ② i:左半起点, j:右半起点
while (i <= mid && j <= right) { // ③ 双指针取较小者
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) temp[k++] = nums[i++]; // ④ 左半剩余
while (j <= right) temp[k++] = nums[j++]; // ⑤ 右半剩余
for (int p = 0; p < temp.size(); p++) { // ⑥ 写回原数组
nums[left + p] = temp[p];
}
}
void mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) return; // ① 递归终止
int mid = left + (right - left) / 2; // ② 取中点
mergeSort(nums, left, mid); // ③ 递归排序左半
mergeSort(nums, mid + 1, right); // ④ 递归排序右半
merge(nums, left, mid, right); // ⑤ 合并两个有序区间
}
时间复杂度：$O(N \log N)$（最好最坏都一样）。 空间复杂度：$O(N)$（合并时需要临时数组）+ $O(\log N)$（递归栈）。
三、自底向上（迭代）归并
整体操作流程：
- 步长控制：
step从 1 开始，每次翻倍（1→2→4→8…），代表当前合并的子数组大小。 - 遍历合并：每次以
step * 2为步长遍历数组，合并相邻的两个长度为step的子数组。 - 计算边界：
mid = left + step - 1是左半的终点，right是右半的终点（不超过数组末尾）。 - 调用 merge：合并
[left, mid]和[mid+1, right]两个有序区间。 - 重复：直到
step ≥ n，整个数组有序。
void mergeSortIterative(vector<int>& nums) {
int n = nums.size();
for (int step = 1; step < n; step *= 2) { // ① 步长 1,2,4,8...
for (int left = 0; left < n - step; left += step * 2) {// ② 每两个子数组为一组
int mid = left + step - 1; // ③ 左半终点
int right = min(left + step * 2 - 1, n - 1);// ④ 右半终点（防越界）
merge(nums, left, mid, right); // ⑤ 合并两个有序区间
}
}
}
自底向上 vs 自顶向下：
- 自底向上：没有递归，没有 $O(\log N)$ 栈空间，只有 $O(N)$ 的临时数组。
- 自顶向下：代码更直观，但递归深度 $\log N$。
四、外部排序——归并排序的核心应用
当数据量超过内存时，快排无法工作（需要随机访问整个数组），归并排序可以。
外部排序流程（假设内存只能存 100 个数，数据有 1000 个数）：
1. 分 10 批，每批 100 个：
读入 100 个 → 快排 → 写回磁盘为 "run1"
读入 100 个 → 快排 → 写回磁盘为 "run2"
... 共 10 个有序文件
2. 多路归并：
同时打开 10 个文件，各读第一个数
选出最小的输出到结果文件，从对应文件读下一个
类似多路归并排序的 merge 步骤
五、面试追问 Q&A
Q1：什么场景必须用归并排序而不是快排？ A：
- 外部排序（数据量 > 内存）：归并排序是唯一选择，快排需要随机访问整个数组。
- 需要稳定排序（相等元素的相对顺序不变）：归并排序天然稳定，快排不稳定。
- 链表排序：归并排序可以在链表上 $O(1)$ 额外空间实现，快排需要随机访问。
Q2：std::stable_sort 的实现是什么？
A：当元素数量足够分配临时内存时，用归并排序。当内存不足时，退化为 归并插入排序（TimSort 的变体）。