Appearance
归并排序（二路归并）
稳定且保证 O(n log n) 的排序
归并排序是唯一一个既稳定又保证 O(n log n) 的比较排序——Java 的 Arrays.sort 对对象数组用的就是它（TimSort 是归并的优化版）。代价是需要 O(n) 的额外空间，这也是它在 408 考试中与堆排序对比的核心考点。
核心思想
归并排序的核心是分治法（Divide and Conquer），包含三个步骤：
- 分解：将待排序数组从中间一分为二，得到两个子数组
- 递归求解：对左右两个子数组分别递归地进行归并排序
- 合并：将两个已排好序的子数组合并为一个有序数组
整个过程可以理解为：先递归地把数组拆到每组只有一个元素（天然有序），然后自底向上不断地将两个有序序列归并为一个更大的有序序列。
原始数组: [8, 4, 5, 7, 1, 3, 6, 2]
分解: [8,4,5,7] [1,3,6,2]
[8,4] [5,7] [1,3] [6,2]
[8][4] [5][7] [1][3] [6][2]
合并: [4,8] [5,7] [1,3] [2,6]
[4,5,7,8] [1,2,3,6]
[1,2,3,4,5,6,7,8]交互可视化
通过下方的交互动画，你可以逐步观察归并排序的执行过程：
操作详解
算法思路
二路归并排序的算法分为两部分：
- Merge 函数：将两个相邻的有序子序列合并为一个有序序列
- MergeSort 函数：递归地将数组一分为二，然后调用 Merge 合并
归并过程详解
Merge 操作是归并排序的核心。给定数组 A[low..mid] 和 A[mid+1..high] 两个有序子序列，将它们合并为一个有序序列：
关键步骤：
- 申请辅助数组
B，将A[low..high]复制到B中 - 设两个指针
i、j分别指向B中左右子序列的起始位置 - 比较
B[i]和B[j]，将较小者放入A[k]，对应指针后移 - 当某一侧耗尽时，将另一侧剩余元素依次放入
A
c
int *B = (int *)malloc((n + 1) * sizeof(int)); // 辅助数组
// 将 A[low..mid] 和 A[mid+1..high] 归并
void Merge(int A[], int low, int mid, int high) {
int i, j, k;
for (k = low; k <= high; k++)
B[k] = A[k]; // 复制到辅助数组
for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
if (B[i] <= B[j]) // ⭐ <= 保证稳定性
A[k] = B[i++];
else
A[k] = B[j++];
}
while (i <= mid) A[k++] = B[i++]; // 左侧剩余
while (j <= high) A[k++] = B[j++]; // 右侧剩余
}注意：比较时使用
<=而非<，这是保证归并排序稳定性的关键。当左右子序列出现相同元素时，优先取左侧元素，保持相对顺序不变。
递归分析
MergeSort 递归地将数组从中间拆分，直到子数组长度为 1，然后逐层归并：
c
void MergeSort(int A[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
MergeSort(A, low, mid); // 左半部分排序
MergeSort(A, mid + 1, high); // 右半部分排序
Merge(A, low, mid, high); // 归并
}
}递归过程形成一棵递归树：
- 第 1 层：1 个长度为 n 的序列 → 拆成 2 个
- 第 2 层：2 个长度为 n/2 的序列 → 各拆成 2 个
- ……
- 第 k 层：2^(k-1) 个长度为 n/2^(k-1) 的序列
- 共 ⌈log₂n⌉ 层（即归并趟数）
每一层的归并操作总共需要比较和移动 O(n) 次，因此总时间复杂度为 O(nlog₂n)。
⚠️ 易错：归并排序的每一趟都是对相邻的有序子表进行两两合并。第 1 趟后每个子表长 2，第 2 趟后长 4...第 k 趟后长 2^k。408 选择题常给出某趟排序后的序列，问"这可能是归并排序第几趟的结果"。
⚠️ 易错：归并排序的比较次数与初始序列无关（始终是 O(n log n)），但移动次数与初始序列有关。这与简单选择排序的"比较次数与初始序列无关"形成对比。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(nlog₂n) | 无论输入如何，都要执行完整的分治过程 |
| 最坏时间 | O(nlog₂n) | 同上，与输入序列无关 |
| 平均时间 | O(nlog₂n) | 三种情况下时间复杂度一致 |
| 空间复杂度 | O(n) | 辅助数组 B 需要 O(n) 空间，递归栈 O(log₂n) |
| 稳定性 | 稳定 | 归并时相同元素优先取左侧，保持相对顺序 |
| 归并趟数 | ⌈log₂n⌉ | 递归树的高度 |
与快速排序的对比：
| 对比项 | 归并排序 | 快速排序 |
|---|---|---|
| 最坏时间 | O(nlog₂n) | O(n²) |
| 平均时间 | O(nlog₂n) | O(nlog₂n) |
| 空间复杂度 | O(n) | O(log₂n) |
| 稳定性 | 稳定 | 不稳定 |
| 适用场景 | 要求稳定性或最坏情况性能保证 | 内部排序，平均性能最优 |
归并排序的时间复杂度在所有情况下都是 O(nlog₂n)，但代价是需要 O(n) 的额外空间。快速排序平均常数因子更小，实际运行更快，但最坏情况会退化。
考研高频考点
- ⭐ 归并排序的时间复杂度：所有情况均为 O(nlog₂n)（选择题/填空题高频）
- ⭐ 归并排序是稳定的排序算法（判断题/选择题必考）
- ⭐ 空间复杂度 O(n)：需要与原数组等长的辅助数组（选择题常考）
- ⭐ 归并趟数为 ⌈log₂n⌉（填空题高频，注意是向上取整）
- ⭐ 归并排序 vs 快速排序的对比（简答题/选择题高频考点）
- 每趟归并的比较次数分析（偶尔出计算题）
- 二路归并的 Merge 操作实现细节（代码填空题）
相关知识
- 归并排序的"先递归后合并"与快速排序的"先划分后递归"形成对称——理解两者的递归结构差异是排序章节的重要考点
- 归并排序是外部排序的基础——当数据量超过内存容量时，外部排序使用多路归并，参见外部排序
- 归并排序的稳定性使其成为需要保持相同关键字相对顺序场景的首选，例如多关键字排序（先按次关键字排序，再按主关键字稳定排序）