Appearance
归并排序（二路归并）
为什么需要归并排序
快速排序虽然平均性能优秀，但最坏情况下时间复杂度会退化为 O(n²)。归并排序基于分治法，在任何情况下都能保证 O(nlog₂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
cpp
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，然后逐层归并：
cpp
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)。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | 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 操作实现细节（代码填空题）