归并排序 (Merge Sort)
采用分治思想的稳定排序算法，结合二叉树后序遍历理解：先递归处理左右子数组，再合并两个有序数组，时间复杂度稳定为 O(n log n)。
定义
归并排序（Merge Sort）是一种基于**分治算法（Divide and Conquer）**的排序算法。其核心思想是：
先递归地将左右两半子数组排好序，然后在后序位置合并两个有序数组。
归并排序的思维模式可以用二叉树的后序遍历来理解：先处理子问题（左右子树），再合并结果（后序位置）。
核心特性
| 特性 | 说明 |
|---|---|
| 排序类型 | 比较排序 |
| 时间复杂度 | O(n log n)，最坏/平均/最好情况都是 |
| 空间复杂度 | O(n)，需要额外数组进行合并 |
| 稳定性 | 稳定排序 |
| 排序方式 | 原地/非原地（典型实现需要额外空间） |
| 思维模式 | 二叉树后序遍历 |
基本原理
算法三步骤
- 分解（Divide）：找到数组中点，将数组分为左右两半
- 解决（Conquer）：对左右两半分别递归调用归并排序
- 合并（Merge）：将两个已排序的子数组合并成一个有序数组
递归结构（类比二叉树后序遍历）
sort(nums, lo, hi)
├─ if lo == hi: return (叶子节点，单个元素天然有序)
├─ mid = (lo + hi) / 2
├─ sort(nums, lo, mid) // 左子树（前序位置）
├─ sort(nums, mid+1, hi) // 右子树（前序位置）
└─ merge(nums, lo, mid, hi) // 后序位置：合并左右子树
合并两个有序数组（核心操作）
使用双指针技巧：
- 指针 i 指向左子数组起始位置
- 指针 j 指向右子数组起始位置
- 比较 nums[i] 和 nums[j]，将较小的放入结果数组
- 重复直到所有元素处理完毕
稳定性保证：遇到相等元素时，先取左子数组的元素，保持原有相对顺序。
时间复杂度/性能
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n log n) | 每次均匀分割数组 |
| 平均情况 | O(n log n) | 递归深度 log n，每层合并 O(n) |
| 最坏情况 | O(n log n) | 归并排序时间复杂度稳定，不会出现像快排的 O(n²) |
| 递归深度 | O(log n) | 每次二分 |
分析：
- 递归树高度：log n（每次二分）
- 每层工作量：O(n)（合并操作需要遍历所有元素）
- 总复杂度：O(n) × O(log n) = O(n log n)
与类似概念对比
| 维度 | 归并排序 | 快速排序 | 桶排序 |
|---|---|---|---|
| 遍历模式 | 二叉树后序遍历 | 二叉树前序遍历 | 分桶 + 桶内排序 |
| 核心思路 | 先递归处理左右，再合并 | 先分区，再递归处理 | 分配 → 排序 → 合并 |
| 时间复杂度 | O(n log n) 稳定 | O(n log n) 平均，O(n²) 最坏 | 取决于桶数量和合并方式 |
| 空间复杂度 | O(n) | O(log n) ~ O(n) | O(k) |
| 稳定性 | 稳定 | 不稳定 | 取决于桶内排序 |
| 是否原地 | 否（典型实现） | 是（原地分区） | 取决于实现 |
注意事项
- 不是原地排序：典型实现需要 O(n) 额外空间用于合并操作
- 递归深度：对于非常大的数组，递归深度可能导致栈溢出（可改为迭代版）
- 适合外部排序：当数据量太大无法一次性加载到内存时，归并排序适合外部排序
应用场景
- 需要稳定排序的场景
- 链表排序（链表归并排序可以原地实现）
- 外部排序（数据量超过内存）
- 需要稳定 O(n log n) 时间复杂度的场景
经典算法
- 归并排序本体：分治 + 后序合并
- 自底向上归并排序：迭代版本，避免递归
- 链表归并排序：对链表进行原地归并排序
- 外部归并排序：用于磁盘文件排序