归并排序（二路归并）

2026 大纲 七（九）二路归并排序（多路归并、败者树、置换-选择、最佳归并树见《外部排序》）。

"归并"是合并，不是划分

先把名字理清楚，这是真题正面问过的一件事：

🔴 二路归并操作的功能是"把两个有序表合并成一个新的有序表"。

它不是"把数组划分成两部分"——那是快速排序的 Partition 干的事。归并排序里确实有"对半切"的动作，但那只是为了递归下去，切的时候什么都不做，真正的工作全在合并。

一趟归并之后的不变量：

序列被切成若干连续段，每段内部有序、段长 $2^k$（最后一段可能不足）。

由此得到两个指纹：

🔴 一趟到位 0 个。 归并不满足"每趟至少一个元素到最终位置"——要到最后一趟才全部就位。这与冒泡、快排、简单选择、堆排全都相反。

🔴 与希尔排序的分界：归并的有序是"连续切一刀"，希尔的有序是"隔 $d$ 跳着看"。判中间状态时先问这一句。

先动手看一眼

加载可视化中...

代码与四处要点

// 把 A[low..mid] 与 A[mid+1..high] 归并；B 是与 A 等长的辅助数组
void Merge(int A[], int B[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++)
        B[k] = A[k];                   // 先整段复制到 B，A 中的位置随后要被覆盖
    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++]; // 右段还有剩余，整体搬回
}

void MergeSort(int A[], int B[], int low, int high) {
    if (low < high) {                     // 长度 >= 2 才需要分
        int mid = (low + high) / 2;       // 左段 A[low..mid]，右段 A[mid+1..high]
        MergeSort(A, B, low, mid);
        MergeSort(A, B, mid + 1, high);
        Merge(A, B, low, mid, high);      // 工作全在回来的路上
    }
}

void MergeSortMain(int A[], int n) {
    if (n <= 1) return;
    int *B = (int *)malloc(n * sizeof(int));   // 辅助数组只申请一次，各层复用
    if (B == NULL) return;
    MergeSort(A, B, 0, n - 1);
    free(B);
}

🔴 第一，为什么必须要辅助数组。 归并是"边读边写同一片区域"：把右段的小元素写到 A[low] 会覆盖掉左段还没读的数据。不复制到 B，就只能靠整段后移腾位置，每次插入都是 $O(n)$，总复杂度退回 $O(n^2)$。"要 $O(n\log n)$ 就得掏 $O(n)$ 空间"是归并排序的定价，不是实现上的偷懒。

第二，两个收尾 while 只会执行其中一个：主循环退出时必然是 i > mid 或 j > high 之一成立，两个都写是为了不必判断哪侧耗尽。

第三，辅助数组在最外层申请一次，各层递归复用同一块 B。若在 Merge 内部申请，$O(n)$ 次 malloc／free 会成为新瓶颈。

第四，稳定性就在 <= 这一个符号上。 把它改成 <：$n=2$、左段 [2a]、右段 [2b]，正确版判断 2a <= 2b 为真先取 2a，输出 2a, 2b；错误版判断 2a < 2b 为假，走 else 先取 2b，输出 2b, 2a。

数一次合并的比较次数

真题给出几个短的升序序列，问按某个次序两两归并的总比较次数。规则只有一条，但很容易数多：

🔴 每一步从两段的头部各取一个比较一次，胜者输出；一旦某一段空了，另一段的剩余元素直接尾接拷贝，不再产生任何比较。

所以合并长度为 $a$、$b$ 的两段，比较次数在 $min(a,b)$ 与 $a+b-1$ 之间——最后一个元素永远不需要比较。

拿一个真题设定走一遍：三个升序序列 $(3,5)$、$(7,9)$、$(6)$，按从左至右的次序两两归并。

第一次合并 $(3,5)\oplus (7,9)$：

步	比较	胜者
1	3 vs 7	3
2	5 vs 7	5
—	左段空，7、9 直接尾接	不比较

2 次，结果 $(3,5,7,9)$。

第二次合并 $(3,5,7,9)\oplus (6)$：

步	比较	胜者
1	3 vs 6	3
2	5 vs 6	5
3	7 vs 6	6
—	右段空，7、9 直接尾接	不比较

3 次，结果 $(3,5,6,7,9)$。

总计 $2+3=5$ 次。 最容易多数的就是那两次"尾接"——它们一次比较都不做。

合并次序会影响总代价：这是哈夫曼树

上一节的合并次序是题目指定的。若次序可以自己选，问"最坏情况下比较的总次数最少是多少"，那就变成了一道哈夫曼树题。

关键换算：合并长度 $a$、$b$ 的两个有序表，最坏比较次数是 $a+b-1$（最后一个元素直接放入，不比较）。而合并结果的长度是 $a+b$，还要参与后续合并。所以

🔴 总比较次数 $=$ 各次合并的长度之和 $=$ 以各表长度为权值的哈夫曼树的 WPL。 最优策略就是每轮挑当前最短的两个表合并。

用真题的数据走一遍：6 个有序表长度分别为 10、35、40、50、60、200，做 5 次两两合并。

轮	当前各表长度	选中合并	合并后	本次最坏比较
1	10, 35, 40, 50, 60, 200	10 + 35	45	$10+35-1=44$
2	40, 45, 50, 60, 200	40 + 45	85	$40+45-1=84$
3	50, 60, 85, 200	50 + 60	110	$50+60-1=109$
4	85, 110, 200	85 + 110	195	$85+110-1=194$
5	195, 200	195 + 200	395	$195+200-1=394$

总计 $44+84+109+194+394=\mathbf{825}$ 次。

⚠️ 口径提示：部分教材把单次合并的代价简化记作 $a+b$（忽略那个 $-1$），按该口径总和是 $45+85+110+195+395=830$。两种口径考研都接受，关键是策略正确（哈夫曼合并）加中间过程清晰。

推广到 $N$ 个不等长有序表：每次挑最短的两个合并，等价于以各表长度为权值构造一棵 $N$ 个叶子的哈夫曼树，自底向上合并。理由：短表参与合并的次数越多、代价越大，所以要让长表尽量晚参与、少参与——这正是哈夫曼树"权大的离根近"的另一种说法。

移动次数固定、比较次数波动

这一对最容易记反，而且方向与简单选择排序恰好相反：

指标	是否依赖初始序列	为什么
移动次数	❌ 不依赖	每个元素每趟必搬一次，与取值无关；总计至多 $n\lceil {\log }_{2}n\rceil$
比较次数	✅ 依赖	一侧提前耗尽就省下若干次；每趟不超过 $n$

穷举验证（$n=8$ 的全部 $8!=40320$ 种排列）：总移动次数恒为 24（$=3$ 趟 $\times 8$），总比较次数在 12 到 17 之间浮动。

常见的记反："归并排序的比较次数与初始序列无关、移动次数有关"——这是把两者对调了。正确的是移动无关、比较有关，而且这个"有关"只是常数级波动，不改变量级。

趟数固定 $\lceil {\log }_{2}n\rceil$，与初始序列无关，段长每趟翻倍。于是时间是最好 = 最坏 = 平均 = $\mathrm{\Theta }(n{\log }_{2}n)$：分治结构由 $n$ 唯一决定，既不会因输入有序而变快，也不会因输入恶劣而变慢。

空间 $O(n)$：辅助数组 $O(n)$ + 递归栈 $O({\log }_{2}n)$，前者主导。这是为"稳定 + 最坏有保证"支付的全部代价。

它能用在链表上，也能用在磁盘上

链表：归并只需要顺序访问，不需要随机存取。而且链表实现连辅助数组都不用——合并时改指针即可，空间降到 $O(1)$（递归版仍有 $O(\log n)$ 栈）。

它是链表上唯一现实可用的 $O(n\log n)$ 排序：快排、堆排、希尔、折半插入都要随机存取。

磁盘：同样因为"只需顺序访问"，归并是外存排序的唯一现实选择。真题问过"对 10TB 的数据文件进行排序应使用什么方法"，答归并排序——不是因为它比较次数少（希尔、堆排、快排在内存里都不慢），而是因为只有它能在数据装不进内存的前提下工作：每次只需把两个归并段的当前块读进内存。完整流程见外部排序。

反过来，在内存里选它而不选插入排序，理由只有"运行效率更高"一条——它的代码更长、占用空间更多（要 $O(n)$ 辅助数组），这两条都是劣势。

逐趟推演：两个手工模拟的例子（想判断中间状态是第几趟就展开）

自底向上的视角在手工推演时更方便：含 $n$ 个记录的初始序列可看成 $n$ 个长度为 1 的有序子序列；两两归并得到 $\lceil n/2\rceil$ 个长度为 2（最后一个可能是 1）的有序子序列；再两两归并……直到得到一个长度为 $n$ 的有序序列。递归视角与自底向上视角产生的趟数与每趟段长完全一致，只是执行次序不同。

原始数组: [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]     ← 第 1 趟，段长 2
          [4,5,7,8]        [1,2,3,6]       ← 第 2 趟，段长 4
          [1,2,3,4,5,6,7,8]                ← 第 3 趟，段长 8

以 {49, 38, 65, 97, 76, 13, 27}（$n=7$）为例（[] 表示一个有序段）：

趟	段长	结果
初始	1	[49] [38] [65] [97] [76] [13] [27]
1	2	[38 49] [65 97] [13 76] [27]
2	4	[38 49 65 97] [13 27 76]
3	8（不足则取全部）	[13 27 38 49 65 76 97]

$n=7$ 时 $\lceil {\log }_{2}7\rceil =3$，与实际趟数吻合。注意每趟末尾可能剩下不足一个完整段的部分（第 1 趟的 [27]），它这一趟不参与归并，原样保留到下一趟。

再看 $n=8$ 的 {3, 8, 7, 4, 1, 5, 2, 6}：

趟	段长	结果
1	2	[3 8] [4 7] [1 5] [2 6]
2	4	[3 4 7 8] [1 2 5 6]
3	8	[1 2 3 4 5 6 7 8]

第 2 趟结束时，序列 3 4 7 8 1 2 5 6 的两个连续 4 元段各自有序——这就是归并排序中间状态的指纹。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 9.18 归并排序过程的示例，p422

这张图把"先递归后合并"画得很直白：左半边（向下的箭头）全程没有做任何比较，只是在切分；真正的工作全在右半边（向上的箭头）。把它与快速排序的递归树对照着看——快排恰好相反，工作全在向下的那一侧。

趟数与两种次数的完整推导，含实测数据（想知道非二的幂时到底差多少就展开）

趟数 $\lceil {\log }_{2}n\rceil$ 的来历。 从递归树看：第 $k$ 层是 $2^{k-1}$ 个长度 $n/2^{k-1}$ 的序列，递归到子序列长度为 1 时停止：

$$\frac{n}{2^{k-1}}=1⟹k-1={\log }_{2}n$$

向上取整是因为 $n$ 不是 2 的幂时，最深那一层只有部分子树存在，但整棵树的高度仍要覆盖它。

$n$	5	7	8	9	16	17
$\lceil {\log }_{2}n\rceil$	3	3	3	4	4	5

移动与比较的细节。 设某趟中要归并的两段总长为 $L$：

• 移动次数恒为 $L$（若把"复制到 B"也算上则是 $2L$）。每个元素不多不少各搬一次。
• 比较次数在 $min(L_1,L_2)$ 与 $L-1$ 之间波动。 教材表述是"每一趟归并，其关键字比较次数不超过 $n$"。

⚠️ "$n\lceil {\log }_{2}n\rceil$"是上界，只有 $n$ 为 2 的幂时才取等。 实测：$n=7$ 实际搬 20 次（式子给 21）、$n=9$ 搬 29 次（给 36）、$n=100$ 搬 672 次（给 700）。而且非 2 幂时递归版与自底向上迭代版的划分方式不同，次数也不同（$n=9$ 分别是 29 与 33）。

这不影响"与初始序列无关"这一条，它严格成立：$n=7$ 的全部 $5040$ 种排列实测移动次数恒为 20。

与快速排序的七维对照：

对比项	归并排序	快速排序
最坏时间	$\mathrm{\Theta }(n{\log }_{2}n)$	$O(n^2)$
平均时间	$\mathrm{\Theta }(n{\log }_{2}n)$	$O(n{\log }_{2}n)$，常数因子更小
空间复杂度	$O(n)$（辅助数组）	$O({\log }_{2}n)\sim O(n)$（递归栈）
稳定性	稳定	不稳定
递归结构	先递归后合并：下去时什么都不做，回来才干活	先划分后递归：下去前先干活，回来什么都不做
对初始序列	完全不敏感	敏感（已有序时最坏）
链表	适用，且省掉辅助数组	难以适用

两个算法的总工作量都是 $O(n\log n)$，差别只在于这些工作放在递归的"下行阶段"还是"上行阶段"。

考点速记

三条结论：

1. "归并"是合并两个有序表，不是划分；一趟到位 0 个，要到最后一趟才全部就位。
2. 移动次数固定、比较次数波动（与简单选择恰好相反）；趟数固定 $\lceil {\log }_{2}n\rceil$。
3. 稳定 + 最坏有保证 + 可用于链表和外存，共同代价是 $O(n)$ 辅助空间。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 二路归并操作的功能是什么：答"将两个有序表合并为一个新的有序表"。三个干扰项都在描述"划分"，那是快速排序。
• 数总比较次数：给几个短的升序序列和归并次序，问关键字之间的总比较次数。一段空了之后剩余元素直接尾接，不再比较——这是最容易多数的地方。
• 合并次序可选时求最小总代价（大题）：$N$ 个不等长有序表两两合并，要求最坏比较总次数最小。用哈夫曼树策略：每轮挑最短的两个合并；单次代价按 $a+b-1$（或 $a+b$，两种口径都接受）。第 2 问要答出策略并说明理由。
• 10TB 数据文件用什么方法排序：答归并排序，理由是只有它能在数据装不进内存时工作。
• 选归并而不选插入的理由：只有"运行效率更高"成立；"代码更短"✗、"占用空间更少"✗。
• 外部排序中 $k$ 路归并的趟数关系：$k$ 越大 $d$ 越小 ✓、初始归并段数不影响 $d$ ✗、内存大小限制初始归并段的最大长度 ✓（详见外部排序）。

易错：尾接不产生比较。 合并长度 $a$、$b$ 的两段，最多比 $a+b-1$ 次，最少 $min(a,b)$ 次。

易错：移动次数与初始序列无关、比较次数有关，别把这一对说反。

易错：归并一趟 0 个元素就位。 "每趟至少确定一个元素最终位置"的题里，归并是被排除的那个。

教材出处

• 二路归并排序的基本思想（"可看成 $n$ 个有序的子序列，每个长度为 1，然后两两归并，得到 $\lceil n/2\rceil$ 个长度为 2 或 1 的有序子序列，如此重复"）、以 $\{49,38,65,97,76,13,27\}$ 为例的逐趟过程（图 8.13）：严蔚敏《数据结构（C 语言版）》（第 2 版），p254
• 相邻两个有序子序列归并的算法步骤与算法描述（算法 8.10 Merge，其中判断用 R[i].key <= R[j].key）、"假设每个子序列的长度为 $h$，则一趟归并排序需调用 $\lceil n/2h\rceil$ 次 merge，整个归并排序需进行 $\lceil {\log }_{2}n\rceil$ 趟"、递归实现（算法 8.11）：同书 p255
• "当有 $n$ 个记录时，需进行 $\lceil {\log }_{2}n\rceil$ 趟归并排序，每一趟归并，其关键字比较次数不超过 $n$，元素移动次数都是 $n$，因此归并排序的时间复杂度为 $O(n{\log }_{2}n)$"；"用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间，所以空间复杂度为 $O(n)$"：同书 p256
• 算法特点："是稳定排序"；"可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈"：同书 p256
• "直接插入排序、归并排序都易于在链表上实现"：同书 p269

相关知识

快速排序（递归结构与归并对称）｜ 堆排序（同样最坏有保证且空间 $O(1)$，但不稳定）｜ 哈夫曼树（多表合并求最小总代价用的就是它）｜ 外部排序（把归并思想搬到磁盘上）｜ 排序的基本概念（稳定性在多关键字排序中的用途）｜ 由中间状态反推排序算法｜ 排序算法对比

相关文章

• 排序基本概念
• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 基数排序
• 计数排序
• 外部排序
• 由中间状态反推排序算法
• 排序算法对比与性能实测

交互体验

前往完整可视化页面 →

真题练习

相关真题（6题）

2026Q112分2024Q102分2022Q102分2017Q102分2016Q112分2012Q4110分