一、排序的四个维度
在比较任何排序算法之前，先约定要比较什么：
| 维度 | 含义 | 为什么重要 |
|---|---|---|
| 时间复杂度 | 最好 / 平均 / 最坏 | 常规指标 |
| 额外空间 | 除输入外的空间；O(1) 称原地（in-place） | 内存受限、缓存 |
| 稳定性（stable） | 相等元素的相对顺序是否保持 | 多关键字排序的基础 |
| 自适应性（adaptive） | 输入近乎有序时是否更快 | 真实数据经常近乎有序 |
⭐ 稳定性为什么重要
假设要"先按部门排、再按工资排"。做法是：先按工资排，再用稳定排序按部门排。稳定性保证第二次排序不会打乱同部门内已排好的工资顺序。
如果排序不稳定，就必须构造复合键 (部门, 工资) 一次排完——可行，但当排序键来自用户交互（点击表头依次排序）时就做不到了。
原始： (销售,8k) (技术,9k) (销售,7k) (技术,6k)
按工资：(技术,6k) (销售,7k) (销售,8k) (技术,9k)
按部门（稳定）： (技术,6k) (技术,9k) (销售,7k) (销售,8k) ✓ 部门内工资仍有序
按部门（不稳定）：(技术,9k) (技术,6k) (销售,8k) (销售,7k) ✗
Go 提供了两套 API：
sort.Slice/slices.SortFunc不稳定（内部是 pdqsort），sort.SliceStable/slices.SortStableFunc稳定（内部是插入排序 + 原地归并）。选错会得到看似正常但偶尔错乱的结果。
二、插入排序
思想：维护一个已排序的前缀，每次把下一个元素插到正确位置。就像整理手中的扑克牌。
[31] 41 59 26 已排序前缀 [31]
[31 41] 59 26 41 插到 31 之后
[31 41 59] 26 59 插到 59 之后
[26 31 41 59] 26 一路左移到最前
func InsertionSort(a []int) {
for j := 1; j < len(a); j++ {
key := a[j]
i := j - 1
for i >= 0 && a[i] > key { // 严格 > 保证稳定
a[i+1] = a[i]
i--
}
a[i+1] = key
}
}
⚠️ 稳定性来自 > 而非 >=：遇到相等元素就停下，不越过它，于是相等元素的原有顺序被保留。把 > 改成 >= 会得到一个仍然正确但不稳定的排序——这是一个字符之差的隐蔽 bug。
正确性证明（循环不变式三段论）见第 1 讲。
精确代价分析
设 tⱼ = 第 j 轮内层循环执行的次数（即 a[j] 左移的距离）：
T(n) = c₁n + c₂(n−1) + c₃ Σⱼ tⱼ + …
| 情况 | tⱼ | T(n) |
|---|---|---|
| 最好（已升序） | 每轮 0 | Θ(n) |
| 最坏（已降序） | 第 j 轮 j−1 次 | Σ(j−1) = n(n−1)/2 = Θ(n²) |
| 平均（随机排列） | 约 j/2 | Θ(n²) |
⭐ 与逆序对的精确关系
定义：数组 A 中满足
i < j且A[i] > A[j]的下标对 (i, j) 称为一个逆序对（inversion）。
定理：插入排序的元素移动总次数恰好等于逆序对数量 I。因此
T(n) = Θ(n + I)
证明：内层循环每执行一次，就把一个逆序对 (i, j) 消掉（且只消掉一个：交换相邻元素恰好改变一个逆序对的状态）。初始有 I 个逆序对，排完为 0，故总移动次数 = I。∎
推论：
- 有序数组 I = 0 ⟹ Θ(n)
- 逆序数组 I = n(n−1)/2 ⟹ Θ(n²)
- 每个元素离正确位置不超过 k 的数组，I ≤ nk ⟹ Θ(nk)
⭐ 最后一条说明插入排序是自适应的：对"近乎有序"的数据它是线性的。这解释了两个重要工程事实：
- 所有工业级排序在小数组（n < 12~32）上都切回插入排序——递归的常数开销大于 n² 与 n log n 的差距，且小数组几乎总是"近乎有序"。
- Timsort（Python、Java 的对象排序） 的整个设计就建立在"真实数据由若干已排序的 run 组成"这个观察上。
三、归并排序
分治三步：
分解（Divide）：把 n 个元素的序列分成两个 n/2 的子序列
解决（Conquer）：递归地排序两个子序列
合并（Combine）：把两个已排序子序列合并成一个
[38 27 43 3 9 82 10]
╱ ╲
[38 27 43] [3 9 82 10]
╱ ╲ ╱ ╲
[38] [27 43] [3 9] [82 10]
╱ ╲ ╱ ╲ ╱ ╲
[27] [43] [3] [9] [82] [10]
╲ ╱ ╲ ╱ ╲ ╱
[27 43] [3 9] [10 82]
╲ ╱ ╲ ╱
[27 38 43] [3 9 10 82]
╲ ╱
[3 9 10 27 38 43 82]
func MergeSort(a []int) {
if len(a) < 2 {
return
}
buf := make([]int, len(a)) // 只分配一次辅助数组
mergeSort(a, buf)
}
func mergeSort(a, buf []int) {
if len(a) < 2 {
return
}
mid := len(a) / 2
mergeSort(a[:mid], buf[:mid])
mergeSort(a[mid:], buf[mid:])
merge(a, buf, mid)
}
func merge(a, buf []int, mid int) {
copy(buf, a) // buf[:mid] 与 buf[mid:] 各自有序
i, j := 0, mid
for k := 0; k < len(a); k++ {
switch {
case i >= mid:
a[k] = buf[j]; j++
case j >= len(a):
a[k] = buf[i]; i++
case buf[j] < buf[i]: // ⚠️ 严格 <：相等时优先取左半，保证稳定
a[k] = buf[j]; j++
default:
a[k] = buf[i]; i++
}
}
}
分析
合并是 Θ(n)：外层循环恰好执行 n 次，每次 O(1)。
递归式（第 3 讲）：
T(n) = 2T(n/2) + Θ(n) ⟹ 主定理情形 2 ⟹ T(n) = Θ(n log n)
递归树视角更直观：树高 log n 层，每层合并总量 Θ(n)。
层 0： ──────── n ──────── n
层 1： ─── n/2 ─── ─── n/2 ─── n
层 2： ─ n/4 ─ ─ n/4 ─ ─ n/4 ─ ─ n/4 ─ n
… …
层 log n： 单元素 n
─────────
总计 n · log n
关键性质：无论输入是什么，都是 Θ(n log n)——最好、平均、最坏三种情况一致。这个可预测性是它在很多场景（数据库外排序、并行排序）被选中的原因。
⚠️ 稳定性依赖 buf[j] < buf[i] 中的严格小于。写成 <= 时相等元素会优先取右半，破坏稳定性。
代价：Θ(n) 额外空间
这是归并排序相对快速排序的主要劣势。
原地归并是可能的（slices.SortStableFunc 用的 symmerge 算法就是），但合并变成 O(n log n)，总复杂度退化到 O(n log²n)，常数也大得多。“稳定 + 原地 + O(n log n)“三者不可兼得——至少目前没有实用的算法同时做到。
四、用归并统计逆序对
这是一个模式的典范：分治算法在排序的"顺便"把另一个问题也解决了。
问题：统计数组中逆序对的数量。朴素做法 Θ(n²)。
观察：逆序对分三类——两个都在左半、两个都在右半、一左一右。前两类由递归解决。第三类可以在合并时统计：
合并时，若从右半取走 buf[j]，说明 buf[j] < buf[i]，
而 buf[i..mid−1] 全都 ≥ buf[i] > buf[j]，
⟹ 一次性贡献 (mid − i) 个逆序对
左半: [3, 27, 38] 右半: [9, 10, 43]
i=1 (27) j=0 (9)
9 < 27 ⟹ 取 9，同时 27 和 38 都比 9 大
⟹ 一次加上 (3 − 1) = 2 个逆序对
func CountInversions(a []int) int64 {
b := append([]int(nil), a...) // 不修改原数组
buf := make([]int, len(b))
return sortCount(b, buf)
}
func sortCount(a, buf []int) int64 {
if len(a) < 2 {
return 0
}
mid := len(a) / 2
inv := sortCount(a[:mid], buf[:mid]) + sortCount(a[mid:], buf[mid:])
copy(buf, a)
i, j := 0, mid
for k := 0; k < len(a); k++ {
switch {
case i >= mid:
a[k] = buf[j]; j++
case j >= len(a):
a[k] = buf[i]; i++
case buf[j] < buf[i]:
inv += int64(mid - i) // ⭐ 关键：左半剩余元素全部与 buf[j] 构成逆序对
a[k] = buf[j]; j++
default:
a[k] = buf[i]; i++
}
}
return inv
}
复杂度 Θ(n log n)，比朴素的 Θ(n²) 好一个量级。
逆序对的实际意义：它是"两个排列有多不一样"的度量（Kendall tau 距离），用于推荐系统排序质量评估、生物信息学中基因组重排距离、以及衡量一个数组"有多接近有序”。
五、两个算法的对比
| 插入排序 | 归并排序 | |
|---|---|---|
| 最好 | Θ(n) | Θ(n log n) |
| 平均 | Θ(n²) | Θ(n log n) |
| 最坏 | Θ(n²) | Θ(n log n) |
| 额外空间 | O(1) | Θ(n) |
| 稳定 | ✓ | ✓ |
| 自适应 | ✓（Θ(n+I)） | ✗（除非改造） |
| 缓存局部性 | 优 | 良（顺序访问，但要来回拷贝） |
| 可并行 | 差 | 好（两个子问题独立） |
| 适合 | n 小、近乎有序 | 大数据、要求稳定、外部排序、并行 |
混合策略：真实世界的排序
几乎没有生产代码用纯粹的单一算法：
func hybridSort(a, buf []int) {
if len(a) <= 16 { // 小数组切插入排序
InsertionSort(a)
return
}
mid := len(a) / 2
hybridSort(a[:mid], buf[:mid])
hybridSort(a[mid:], buf[mid:])
if a[mid-1] <= a[mid] { // 已经有序，跳过合并
return
}
merge(a, buf, mid)
}
两个优化都很典型：
- 小数组切插入排序：省掉递归开销，n log n 的优势在 n < 16 时不存在。
- 有序检测：
a[mid-1] <= a[mid]时两半已首尾衔接，直接返回。这一行让近乎有序的输入接近 Θ(n)。
Timsort（Python sorted、Java Arrays.sort 对象版）把这个思路推到极致：先扫描出天然的升序 run（降序则原地反转），短 run 用二分插入排序补到最小长度，然后按一套栈上的平衡规则合并 run。真实数据上常常远快于 Θ(n log n)。
六、外部排序：归并排序的真正主场
当数据大到放不进内存（第 18 讲的外存模型），归并是唯一现实的选择：
① 分块：读入内存装得下的一块 → 内存里排序 → 写回磁盘成为一个有序 run
② 多路归并：同时打开 k 个 run，用一个大小为 k 的最小堆（第 10 讲）
每次取出全局最小写入输出
为什么不是快速排序？ 因为快排需要随机访问整个数组，而归并只需要顺序读每个 run——顺序 I/O 比随机 I/O 快两个数量级。外部排序的瓶颈是磁盘，而归并的访问模式恰好是磁盘最喜欢的那种。
随堂自测
- 为什么插入排序内层条件必须写
a[i] > key而不是>=？改成>=会破坏什么性质？ - 证明插入排序的移动次数恰好等于逆序对数量。用这条结论解释"近乎有序数组上它是线性的”。
- 数组
[5, 1, 4, 2, 3]有多少个逆序对？插入排序在它上面会移动多少次？ - 归并排序的 merge 中，为什么
buf[j] < buf[i]不能写成<=？ - 为什么归并排序最好、平均、最坏都是 Θ(n log n)，而快速排序不是？
- 用递归树论证归并排序的 Θ(n log n)，说明"每层总量 Θ(n)、共 log n 层"这两个事实各自从哪来。
- 手工追踪
CountInversions([2, 4, 1, 3, 5])的每次合并，写出每步累加的逆序对数。 - 为什么外部排序用归并而不是快排？请从 I/O 访问模式角度回答。
slices.SortFunc和slices.SortStableFunc有什么区别？什么时候必须用后者？