入门：分治、稳定与 O(n log n) 三态一致
基于通用算法概念 · 核于 2026-07
速查
- 定义：归并排序是分治算法——把数组对半切成两段，各自递归排序，再用一次 O(n) 的 merge 把两个有序段合并成一个有序整体。
- 递归式：
T(n) = 2·T(n/2) + O(n)，由主定理得 T(n) = O(n log n)——递归树高 log₂ n，每层合并工作量共 n。 - 三态一致：最好、平均、最坏全是 O(n log n)——分治结构固定（必然切到单元素），merge 必然扫满，没有「运气成分」，这是它对快排的最大优势。
- 稳定排序：merge 时「左半元素 ≤ 右半则先取左半」的规则保证相等元素相对次序不变——前提是合并比较写成
<=（左半优先）而非<。 - 空间复杂度 O(n)：merge 需要一个长度为 n 的临时数组；递归栈另占 O(log n)。不是原地排序。
- 两种写法：自顶向下（递归：分半→排→merge，最直观）；自底向上（迭代：从 1 元素两两 merge，步长 1→2→4→…→n，无递归）。
- merge 操作：双指针
i、j分别指向左右两段，每次比较放小者进结果，是「分离指针」的经典应用。 - 与快排对比：归并 稳定 / 非原地 / O(n log n) 一致 / O(n) 辅助空间；快排 不稳定 / 原地 / 平均 O(n log n) 最坏 O(n²) / O(log n) 栈空间。
- 与堆排对比：归并稳定但 O(n) 空间；堆排原地 O(1) 空间但不稳定且常数大。
- 何时选归并：需要稳定性（数据库、多关键字排序）、对最坏情况敏感（实时/对抗输入）、做外排序或链表排序时首选归并。
- 库实现现状：Python
sorted/list.sort用 Timsort（归并 + 插入）；Java 对象排序用 Timsort、基本类型用双轴快排；C++std::stable_sort用归并，std::sort用内省排序（快排+堆排）。 - 进阶顺序：分治与合并 → 应用：逆序对、外排序与 Timsort → 参考。
一、分治思想：分两半、各自排、再合并
归并排序的精髓是把「排序 n 个元素」分解成两个规模减半的同类问题，再用一个高效的 merge 把结果拼回去。整个过程可以用一棵递归树描述：
[8,5,2,6,3,7,1,4] ← 待排序
/ \
[8,5,2,6] [3,7,1,4] ← 对半切（分）
/ \ / \
[8,5] [2,6] [3,7] [1,4] ← 继续分
/ \ / \ / \ / \
[8] [5] [2] [6] [3] [7] [1] [4] ← 单元素天然有序（递归基）
\ / \ / \ / \ /
[5,8] [2,6] [3,7] [1,4] ← merge（治）
\ / \ /
[2,5,6,8] [1,3,4,7] ← 再 merge
\ /
[1,2,3,4,5,6,7,8] ← 最终 merge三个要点：
- 递归基：长度为 1（或 0）的段天然有序，直接返回——这是递归的终止条件。
- 分：
mid = (left + right) >> 1，对[left, mid]和[mid+1, right]递归排序。 - 治（merge）：把两个已排序的段用一个临时数组合并成一个有序段，写回原数组。
二、复杂度：为什么是 O(n log n) 且三态一致
用递归式分析：T(n) = 2·T(n/2) + O(n)。展开后是一棵高度 log₂ n 的二叉树，每层所有 merge 的总工作量恰好是 n（因为每层处理的元素总数不变），共 log₂ n 层，故 T(n) = O(n log n)。
关键：最好、平均、最坏全相同——
- 切分逻辑固定（永远对半切），递归树形状不随输入数据变化，树高恒为 ⌈log₂ n⌉。
- merge 在任何情况下都要扫满两段（即使已经有序也要逐个比较/复制），每层工作量恒为 n。
所以无论输入是已排序、逆序、随机还是精心构造的「毒药」输入，归并排序都是 O(n log n)。这跟快排形成鲜明对比：快排的 pivot 选得差时递归树退化为链，最坏 O(n²)。
注意：可以让「已经有序」的输入跑得更快——merge 前先判断「左段最后元素 ≤ 右段首元素」则直接拷贝无需合并，这样最好情况降到 O(n)。但这是工程优化，标准归并的三态仍是 O(n log n)。
三、稳定性：merge 规则决定一切
稳定排序指相等元素排序后保持原有相对次序。归并的稳定性完全由 merge 的比较方向决定：
// ✅ 稳定写法：左半元素 ≤ 右半时，优先取左半（相等也取左半）
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
// ❌ 不稳定写法：写成 < 会把右半的相等元素提前取走，破坏次序
if (a[j] < a[i]) tmp[k++] = a[j++];
else tmp[k++] = a[i++];为什么「≤ 取左半」就稳定？因为左半元素在原数组中本来就排在右半前面，相等时让左半先落位，相对次序自然保持。这是归并排序作为「稳定排序」的根本保证——也是它被数据库、多关键字排序选中的核心原因。
四、空间：O(n) 辅助数组，非原地
merge 需要把两个有序段合并到一个新序列里再写回原数组，这个过程需要一个长度为 n 的临时数组（合并 [left,right] 段需要 right-left+1 长度的辅助空间）。整个排序过程中这个临时数组可以全局复用（不必每次 merge 都新建），但大小仍是 O(n)。
空间 = O(n) 辅助数组 + O(log n) 递归栈 ≈ O(n)对比：
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 |
|---|---|---|---|---|
| 归并排序 | O(n log n) | O(n log n) | O(n) | 是 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 否 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 |
这就是「排序三件套」最核心的权衡表：归并赢在稳定 + 最坏可控，快排赢在原地 + 常数小，堆排赢在原地 + 最坏可控但常数大、不稳定。
五、与快排怎么选
| 维度 | 归并排序 | 快速排序 |
|---|---|---|
| 平均时间 | O(n log n) | O(n log n)（常数更小） |
| 最坏时间 | O(n log n) ✅ | O(n²) ❌（pivot 选差） |
| 空间 | O(n)（辅助数组）❌ | O(log n)（栈）✅ |
| 原地 | 否 ❌ | 是 ✅ |
| 稳定 | 是 ✅ | 否 ❌ |
| 实际速度 | 较慢（拷贝开销） | 较快 ✅ |
选型口诀：「要稳定 / 怕最坏退化 / 做外排序或链表排序 → 归并；要原地 / 求平均最快 / 内存敏感 → 快排」。这也是为什么各语言库的实现五花八门——Python/Java 对象要稳定用 Timsort（归并系），C++/Java 基本类型求快用快排系（内省排序/双轴快排）。
下一步
理解了归并的分治思想与三态一致的复杂度后，下一步是看它的两种工程写法——自顶向下递归与自底向上迭代，以及 merge 操作的双指针细节，见分治与合并。