OI-wiki 归并排序全解析：稳定分治排序、合并过程与逆序对计数

OI-wiki 归并排序全解析：稳定分治排序、合并过程与逆序对计数

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

归并排序（Merge Sort）是 OI / ICPC 中最重要的基于比较的稳定排序算法之一，本文以 OI-wiki 的 merge-sort 章节 为主体，系统讲解其定义、复杂度性质、合并（merge）核心过程、递归与倍增两种实现方式，并深入其在 O(n log n) 时间内统计逆序对这一竞赛高频应用，同时结合本仓库中的参考实现与分治专题进行源码级佐证。读完本文，你将掌握可稳定复用的归并排序模板，以及用归并过程顺带求解逆序数的完整方案。

定义与基本性质

定义

归并排序（merge sort）是一种高效的、基于比较的稳定排序算法：它能保证排序前后相等元素的相对次序不变，这是它与快速排序、堆排序相比的重要优势，也是它在很多要求「稳定」的题目中被优先选用的原因。

时间复杂度与空间复杂度

归并排序基于分治思想：将数组分段排序后合并。其复杂度特征可以总结为：

• 时间复杂度：最优、最坏与平均情况下均为 $\Theta(n \log n)$。无论输入数据如何分布，归并排序总是严格地把问题对半拆分，因此不存在快速排序那样「退化为 $O(n^2)$」的最坏情形；
• 空间复杂度：$\Theta(n)$。归并排序需要与原数组等长的辅助数组来暂存合并结果，这也是它相对原地排序算法（如堆排序）的主要代价。

需要指出的是，从理论上归并排序可以只使用 $\Theta(1)$ 的辅助空间（即原地归并），但实现复杂且常数较大。正如 OI-wiki 所述，为便捷通常使用与原数组等长的辅助数组。在竞赛中，使用辅助数组的 $O(n \log n)$ 时间 + $O(n)$ 空间版本是标准做法，也是后续所有参考实现的基础。

与分治思想的关系

归并排序是分治法的典型范例。在仓库的 divide-and-conquer.md 中，归并排序被用来示例分治的套路：分解 -> 解决（触底）-> 合并（回溯）。其递归结构形如二叉树的后序遍历：先左右分解，再处理合并，回溯即退栈。仓库中以 C++ 和 Python 分别给出了递归与非递归两种merge_sort写法（见 divide-and-conquer.md），其中非递归版本正是下文将要讲解的「倍增法」。

核心过程：合并（Merge）

归并排序最核心的部分是合并（merge）过程：将两个有序数组a[i]和b[j]合并为一个有序数组c[k]。

合并算法描述

从左往右枚举a[i]和b[j]：

1. 找出当前两个数组首元素中的最小值，放入c[k]；
2. 重复上述过程，直到a和b中有一个数组为空；
3. 将另一个数组剩下的元素依次放入c[k]。

稳定性的关键：比较符号的选择

合并过程的比较符号直接决定排序的稳定性：当前段首元素小于或等于后段首元素（a[i] <= b[j]）时，而非小于时（a[i] < b[j]），就要把前段元素作为最小值放入c[k]。

用代码语言表达就是：先判断后段是否严格小于前段（b[j] < a[i]），只有后段严格更小才取后段，否则取前段。这样相等元素永远是「前段的先被取走」，从而保证相等元素的原始相对次序在合并后不被破坏。

实现一：数组下标实现（C/C++）

void merge(const int *a, size_t aLen, const int *b, size_t bLen, int *c) { size_t i = 0, j = 0, k = 0; while (i < aLen && j < bLen) { if (b[j] < a[i]) { // <!> 先判断 b[j] < a[i]，保证稳定性 c[k] = b[j]; ++j; } else { c[k] = a[i]; ++i; } ++k; } // 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中 for (; i < aLen; ++i, ++k) c[k] = a[i]; for (; j < bLen; ++j, ++k) c[k] = b[j]; }

实现二：指针实现（C/C++）

void merge(const int *aBegin, const int *aEnd, const int *bBegin, const int *bEnd, int *c) { while (aBegin != aEnd && bBegin != bEnd) { if (*bBegin < *aBegin) { *c = *bBegin; ++bBegin; } else { *c = *aBegin; ++aBegin; } ++c; } for (; aBegin != aEnd; ++aBegin, ++c) *c = *aBegin; for (; bBegin != bEnd; ++bBegin, ++c) *c = *bBegin; }

指针版本用「半开区间」[begin, end)描述两个待合并的有序段，语义更贴近 C++ 迭代器风格，也便于直接用于递归与倍增实现。

实现三：使用标准库 merge

C++ 的<algorithm>库提供了现成的merge函数，用法与上述指针式写法相同（传入两段半开区间与输出位置），可直接替代手写合并，减少出错概率：

#include <algorithm> // merge(first1, last1, first2, last2, d_first); std::merge(a + l, a + mid, a + mid, a + r, tmp + l);

实现四：Python 实现

def merge(a, b): i, j = 0, 0 c = [] while i < len(a) and j < len(b): # <!> 先判断 b[j] < a[i]，保证稳定性 if b[j] < a[i]: c.append(b[j]) j += 1 else: c.append(a[i]) i += 1 # 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中 c.extend(a[i:]) c.extend(b[j:]) return c

Python 版本利用切片a[i:]、b[j:]直接追加剩余元素，代码更简洁；注意稳定性判断与 C/C++ 版本完全一致。

分治法（递归）实现归并排序

算法流程

1. 边界条件：当数组长度为 $1$ 时，该数组已经是有序的，不需要再分解；
2. 递归分解：当数组长度大于 $1$ 时，将该数组分为两段，分别对两段递归排序；
3. 合并：将两个有序子段合并为一个有序数组。

用数学归纳法可以证明，该流程能够将任意数组转变为有序数组。为了保证 $O(n \log n)$ 的复杂度，通常将数组分为尽量等长的两段，即取

$$ mid = \left\lfloor \dfrac{l + r}{2} \right\rfloor. $$

实现（C/C++）

注意下面的代码所表示的区间分别是 $[l, r)$、$[l, mid)$、$[mid, r)$：

void merge_sort(int *a, int l, int r) { if (r - l <= 1) return; // 分解 int mid = l + ((r - l) >> 1); merge_sort(a, l, mid), merge_sort(a, mid, r); // 合并 int tmp[1024] = {}; // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用 // vector；先将合并的结果放在 tmp 里，再返回到数组 a merge(a + l, a + mid, a + mid, a + r, tmp + l); // pointer-style merge for (int i = l; i < r; ++i) a[i] = tmp[i]; }

几点实用提示：

• 区间约定：全程采用左闭右开区间 $[l, r)$，mid = l + ((r - l) >> 1)在求中点时避免了(l + r)可能产生的整数溢出，是竞赛中的推荐写法；
• 临时数组：示例中的tmp[1024]仅为示意，实际使用时应将tmp的长度设置为与a相同，或直接使用std::vector<int> tmp(n)动态分配；
• 拷贝回写：合并结果先写入tmp，再统一拷回a[l..r)，避免合并过程中覆盖尚未读取的原元素。

实现（Python）

def merge_sort(a, ll, rr): if rr - ll <= 1: return # 分解 mid = (rr + ll) // 2 merge_sort(a, ll, mid) merge_sort(a, mid, rr) # 合并 a[ll:rr] = merge(a[ll:mid], a[mid:rr])

Python 利用切片赋值直接完成「合并后回写」两步，与 C++ 版本逻辑一一对应。

倍增法（自底向上、迭代）实现归并排序

递归实现需要调用栈的辅助空间，且对栈深度敏感；倍增法则完全不使用递归，自底向上逐层合并，是归并排序的迭代实现。

算法流程

1. 初始状态：已知长度为 $1$ 的数组是有序的，将整个数组视作若干长度为 $1$ 的有序段；
2. 逐层倍增：
   • 从左往右依次合并两个长度为 $1$ 的有序段，得到一系列长度 $\le 2$ 的有序段；
   • 再从左往右依次合并两个长度 $\le 2$ 的有序段，得到一系列长度 $\le 4$ 的有序段；
   • 重复上述过程（段长 $1 \to 2 \to 4 \to \cdots$），直至数组只剩一个有序段。

关于「$\le n$ 而不是 $= n$」

数组的长度很可能不是 $2^x$，此时在最后几轮就可能出现长度不完整的段，甚至出现最后一个段独立存在、没有配对对象的情况。因此每一轮合并出的段长度是「不超过 $2^k$」，而非严格等于 $2^k$。

实现（C/C++）

void merge_sort(int *a, size_t n) { int tmp[1024] = {}; // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用 // vector；先将合并的结果放在 tmp 里，再返回到数组 a for (size_t seg = 1; seg < n; seg <<= 1) { for (size_t left1 = 0; left1 < n - seg; left1 += seg + seg) { // n - seg: 如果最后只有一个段就不用合并 size_t right1 = left1 + seg; size_t left2 = right1; size_t right2 = std::min(left2 + seg, n); // <!> 注意最后一个段的边界 merge(a + left1, a + right1, a + left2, a + right2, tmp + left1); // pointer-style merge for (size_t i = left1; i < right2; ++i) a[i] = tmp[i]; } } }

实现要点：

• 外层循环seg表示当前段长，每轮翻倍（seg <<= 1）；
• 内层循环每次取出两个相邻段 $[left1, right1)$ 与 $[left2, right2)$ 进行合并；
• 边界处理：left1 < n - seg保证「最后若只剩下一个独立段则无需合并」；right2 = std::min(left2 + seg, n)防止第二段越界，这是迭代写法中最容易出错的地方；
• 合并结果同样先写入tmp再回拷到a。

实现（Python）

def merge_sort(a): seg = 1 while seg < len(a): for l1 in range(0, len(a) - seg, seg + seg): r1 = l1 + seg l2 = r1 r2 = l2 + seg a[l1:r2] = merge(a[l1:r1], a[l2:r2]) seg <<= 1

与 C++ 版本等价，只是循环用range表达、合并用切片赋值完成。仓库 divide-and-conquer.md 中的非递归merge_sort（使用std::merge/ Pythonmerge）也采用了同样的「段长倍增」思路，可作为对照阅读。

进阶应用：用归并排序统计逆序对

逆序对的定义

逆序对是满足 $i < j$ 且 $a_i > a_j$ 的有序数对 $(i, j)$。排序后的数组无逆序对；一个排列中逆序对的总数称为该排列的逆序数。逆序数问题在排列组合、概率论与各类计数题中频繁出现，相关理论背景见仓库的 permutation.md 逆序数章节。

原理：合并过程天然携带逆序信息

归并排序的合并操作中，每次后段首元素被作为当前最小值取出时，说明它小于前段所有剩余元素——这些「前段剩余元素」的数量之和，正是合并操作减少的逆序对数量。具体地：

• 当nums[j] < nums[i]（后段元素更小）时，前段区间[i, m)中所有元素都大于nums[j]，因此本次合并贡献m - i个逆序对；
• 归并排序的分治结构保证每个数对恰好被统计一次，因此可以在排序的同时求出全部逆序对数，时间复杂度仍为 $\Theta(n \log n)$。

仓库参考实现

仓库在 docs/math/code/permutation/inversion_2.cpp 中提供了完整的「归并排序求逆序数」参考实现，其关键代码为：

while (i < m && j < e) { if (nums[j] < nums[i]) { tmp[k] = nums[j++]; // In this case, all elements in [i,m) are larger than element j. res += m - i; } else { tmp[k] = nums[i++]; } ++k; }

注意两点：

1. 计数发生在「后段元素被取出」分支中，累加量为m - i（前段剩余元素个数）；
2. 逆序对数量可能超过int范围（如完全逆序排列），参考实现使用long long存储结果，实际题目中应同样注意数据范围。

该实现位于 permutation.md 的参考实现折叠块中，对应输入为n和长度为n的序列，输出逆序数。

其他解法

逆序对计数还可以通过树状数组或线段树解决，时间复杂度同为 $O(n \log n)$：按值域建树，从左到右扫描，每扫到一个元素先查询「比它大的已出现元素个数」，再将其加入树状数组。算法详细解释参见仓库的 fenwick.md 全局逆序对（全局二维偏序）章节，其参考实现同样收录在 permutation.md 中（inversion_1.cpp，树状数组版本）。归并排序方案与数据结构方案各有取舍：前者实现直观、常数小且无需离散化；后者在「二维偏序」类扩展问题上更通用。

在 OI-wiki 中的延伸阅读

归并排序并非孤立知识点，它在本仓库多个专题中承担了承上启下的角色：

• 分治专题：divide-and-conquer.md 以归并排序为第一个示例，讲解分治的「分解 -> 解决 -> 合并」套路，并给出递归/非递归两种写法与「merge_sort类似二叉树后序遍历」的直觉；
• 排列与逆序数：permutation.md 逆序数 给出了逆序数的严格定义（与置换奇偶性的联系）以及归并排序、树状数组两种参考实现；
• 树状数组：fenwick.md 全局逆序对 从数据结构角度再次解决逆序对问题，可与此处归并排序解法对照学习；
• 排序总览：sort-intro.md 对各类排序算法的适用场景做了横向比较，可用于判断何时选用归并排序；
• 其他排序专题：归并排序的「段合并」思想还延伸出 tim-sort.md 等混合排序算法，可作进阶阅读。

掌握了本文的合并写法、递归/倍增两种框架与逆序对计数技巧，你便拥有了应对「稳定排序」「区间有序合并」「二维偏序计数」等一类题目的通用工具箱。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki