归并排序（Merge Sort）
归并排序的重点不是“拆得很细”，而是“两个有序数组怎么线性合并成一个更大的有序数组”。
定义
归并排序是一种分治排序算法，采用”分而治之”的策略：将数组分成两半，分别排序，然后合并两个有序数组。
核心思路
- 分解：将数组递归地分成两半，直到每个子数组只有一个元素
- 解决：单个元素天然有序
- 合并：将两个有序子数组合并成一个有序数组
原数组: [38, 27, 43, 3, 9, 82, 10]
分解:
[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43, 3] | [9, 82, 10]
[38, 27] [43, 3] | [9, 82] [10]
[38] [27] [43] [3] | [9] [82] [10]
合并:
[27, 38] [3, 43] | [9, 82] [10]
[3, 27, 38, 43] | [9, 10, 82]
[3, 9, 10, 27, 38, 43, 82]
🎞️ 分解与合并动画
（附件 merge-sort-split-merge.svg 未随站点发布）
看这个动画时要重点看“合并”阶段
真正把无序变成有序的，不是拆分动作，而是每次从两个有序子数组头部取较小值的过程。
为什么归并一定正确
归并排序的关键不变量是：
- 递归返回时，左右子数组都已经各自有序。
- 合并时，左右指针始终指向各自还没被放入结果中的最小元素。
- 每次把两边较小的那个放进结果，结果数组前缀就始终保持有序。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(n log n) | 总是递归log n层 |
| 平均时间 | O(n log n) | 同上 |
| 最坏时间 | O(n log n) | 性能稳定 |
| 空间复杂度 | O(n) | 需要额外数组存储 |
| 稳定性 | ✅ 稳定 | 合并时保持相对顺序 |
Go 代码
Go 实现
package main
import "fmt"
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := mergeSort(arr[:mid])
right := mergeSort(arr[mid:])
return merge(left, right)
}
func merge(left, right []int) []int {
result := make([]int, 0, len(left)+len(right))
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] <= right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
func main() {
arr := []int{38, 27, 43, 3, 9, 82, 10}
fmt.Println("原始数组:", arr)
sorted := mergeSort(arr)
fmt.Println("排序后:", sorted)
}算法优化
复用临时数组
如果每次 merge 都新建切片，常数开销会比较大。做题或工程实现里，可以预先申请一块临时数组，在递归过程中反复复用。
链表排序时优先考虑归并
数组上的归并有额外空间代价，但链表做归并通常很自然，因为拆链和合并链都比较顺手。
经典题目
基础应用
归并思想应用
- 数组中的逆序对 - 剑指 Offer 51
- 翻转对 - LeetCode 493
- 计算右侧小于当前元素的个数 - LeetCode 315
合并操作
易错点
归并排序的核心 bug 通常都出在 merge 逻辑，而不是递归框架。
- 合并结束后别忘了把剩余元素全部追加进去。
- 想保稳定性时，比较条件要写成
<=，让左边相等元素先出。 - 递归返回的必须是“已经排好序的子问题结果”。
- 如果写原地版本，一定要特别小心覆盖顺序。
优缺点
优点
- ✅ 时间复杂度稳定：保证 O(n log n)
- ✅ 稳定排序：相等元素保持相对顺序
- ✅ 性能可预测
- ✅ 适合外部排序（处理大文件）
- ✅ 易于并行化
缺点
- ❌ 空间复杂度 O(n)：需要额外数组
- ❌ 对小数组性能不如插入排序
- ❌ 不是原地排序
- ❌ 递归开销
应用场景
- 稳定性要求：需要保持相等元素顺序
- 外部排序：数据量大，无法全部载入内存
- 链表排序：归并排序特别适合链表
- 并行排序：容易拆分成多个独立任务
- 时间保证：需要稳定的 O(n log n) 性能
归并排序的实际应用
归并排序 vs 快速排序
| 特性 | 归并排序 | 快速排序 |
|---|---|---|
| 平均时间 | O(n log n) | O(n log n) |
| 最坏时间 | O(n log n) | O(n²) |
| 空间 | O(n) | O(log n) |
| 稳定性 | 稳定 | 不稳定 |
| 实际性能 | 较慢 | 通常更快 |
| 适合场景 | 链表、外部排序 | 数组、一般排序 |