从 TimSort 到 pdqsort：生产级排序算法的工程优化

Paul 收录于 Go

2018-06-21 约 2089 字预计阅读 5 分钟

教科书上的快排只是起点。真实世界的排序算法经过了数十年的工程优化。这篇文章深入分析 Python 的 TimSort 和 Go/Rust 的 pdqsort，揭示"工业级"与"教科书级"的差距。

一、教科书排序的局限

1.1 快排的理想与现实

教科书版快排：

1
2
3
4
5
6
7
func quickSort(arr []int, low, high int) {
    if low < high {
        pivot := partition(arr, low, high)
        quickSort(arr, low, pivot-1)
        quickSort(arr, pivot+1, high)
    }
}

理论：平均 O(n log n)，原地排序，很完美。

现实问题：

最坏 O(n²)：有序/逆序数组会退化
递归开销：深度可达 n 层，栈溢出风险
缓存不友好：随机访问模式
不稳定：相等元素顺序可能改变

1.2 不同语言的选择

语言	默认排序算法	特点
Python	TimSort	稳定、利用已有序列
Go 1.19+	pdqsort	快、不稳定、避免最坏情况
Rust	pdqsort	同 Go
Java	TimSort (对象) / DualPivot (原始类型)	分情况优化
C++	IntroSort	快排 + 堆排混合

二、TimSort：为真实数据设计

2.1 核心洞察

TimSort 的设计者 Tim Peters (Python 核心开发者) 观察到：

“真实世界的数据往往部分有序”

用户按时间排序的日志、按 ID 排序的数据库记录、追加写入的数据——都有"跑道"(run) 特征。

2.2 算法结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
输入: [1, 2, 3, 8, 7, 6, 5, 10, 11, 12]

Step 1: 识别 runs
  Run 1: [1, 2, 3] (升序)
  Run 2: [8, 7, 6, 5] → 翻转为 [5, 6, 7, 8]
  Run 3: [10, 11, 12] (升序)

Step 2: 合并 runs (归并排序)
  [1, 2, 3] + [5, 6, 7, 8] → [1, 2, 3, 5, 6, 7, 8]
  + [10, 11, 12] → [1, 2, 3, 5, 6, 7, 8, 10, 11, 12]

2.3 关键优化

1. 最小 run 长度

如果 run 太短，使用插入排序扩展到 minrun（通常 32-64）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# CPython 源码 (简化)
def binary_insertion_sort(arr, lo, hi, start):
    """在 [lo, hi) 中使用二分插入排序"""
    for i in range(start, hi):
        pivot = arr[i]
        # 二分查找插入位置
        left, right = lo, i
        while left < right:
            mid = (left + right) // 2
            if arr[mid] > pivot:
                right = mid
            else:
                left = mid + 1
        # 移动元素
        arr[left+1:i+1] = arr[left:i]
        arr[left] = pivot

为什么对小数组用插入排序？

常数因子小
缓存友好（顺序访问）
对近乎有序数据 O(n)

2. Galloping Mode (奔腾模式)

合并两个 run 时，如果一个 run 持续"获胜"，说明数据分布不均匀：

1
2
3
4
5
# 普通合并：逐个比较
[1, 2, 3, 4, 100] + [50, 51, 52, 53, 54]

# 发现 run1 持续比 run2 小后，切换到 galloping：
# 指数搜索找到 100 应该插入 [50, 51, 52, 53, 54] 的位置

3. run 栈的平衡

TimSort 维护一个 run 栈，遵循"归并策略"确保平衡合并：

1
2
3
4
5
规则（从栈顶往下数）:
  A > B + C
  B > C

违反则合并，保证栈高度 O(log n)

2.4 性能特征

场景	时间复杂度
完全有序	O(n)
逆序	O(n) (翻转)
随机	O(n log n)
部分有序	介于 O(n) 和 O(n log n)

稳定性：保证相等元素顺序不变，对象排序友好。

三、pdqsort：现代快排的巅峰

3.1 设计目标

pdqsort (Pattern-Defeating Quicksort) 的目标：

平均性能接近快排
最坏情况 O(n log n)
识别特殊 pattern 加速
不稳定但极快

3.2 核心技术

1. 自适应 pivot 选择

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// Go 源码 (sort 包) 简化
func choosePivot(data []int, a, b int) int {
    l := b - a
    
    // 小数组：取中间
    if l < 8 {
        return a + l/2
    }
    
    // 中等数组：三点取中
    if l < 50 {
        m := a + l/2
        return medianOfThree(data, a, m, b-1)
    }
    
    // 大数组：ninther (9点取中)
    m := a + l/2
    return ninther(data, a, m, b-1)
}

2. 坏 pivot 检测

如果 pivot 分割太不均匀（<1/8），说明可能遇到"杀手输入"：

1
2
3
4
5
6
7
8
if partitionSize < length/8 {
    badPivotCount++
    if badPivotCount >= maxBadPivots {
        // 切换到堆排序，保证 O(n log n)
        heapSort(data, a, b)
        return
    }
}

这就是"Pattern-Defeating"的含义：检测并击败试图触发最坏情况的输入。

3. 相等元素分区 (Dutch National Flag)

1
2
3
4
5
6
输入: [5, 3, 5, 7, 5, 2, 5]
pivot = 5

三向分区:
[2, 3] [5, 5, 5, 5] [7]
 < 5       = 5       > 5

对有大量重复元素的数组，直接跳过中间部分。

4. 小数组优化

1
2
3
4
5
// 元素少于 12 个时，用插入排序
if b-a < 12 {
    insertionSort(data, a, b)
    return
}

3.3 Go 1.19 的 sort 包源码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// src/sort/zsortinterface.go
func pdqsort(data Interface, a, b, limit int) {
    const maxInsertion = 12
    
    for {
        length := b - a
        
        // 小数组用插入排序
        if length < maxInsertion {
            insertionSort(data, a, b)
            return
        }
        
        // bad pivot 太多，切换堆排序
        if limit == 0 {
            heapSort(data, a, b)
            return
        }
        
        // 选 pivot 并分区
        pivot := choosePivot(data, a, b)
        mid := partition(data, a, b, pivot)
        
        // 检测 bad partition
        if mid-a < length/8 || b-mid < length/8 {
            limit--
        }
        
        // 递归（尾递归优化：小的递归，大的循环）
        if mid-a < b-mid {
            pdqsort(data, a, mid, limit)
            a = mid + 1
        } else {
            pdqsort(data, mid+1, b, limit)
            b = mid
        }
    }
}

四、性能对比实测

4.1 测试代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func BenchmarkSorts(b *testing.B) {
    sizes := []int{100, 1000, 10000, 100000}
    patterns := []string{"random", "sorted", "reversed", "partial", "duplicates"}
    
    for _, size := range sizes {
        for _, pattern := range patterns {
            b.Run(fmt.Sprintf("%s-%d", pattern, size), func(b *testing.B) {
                data := generateData(pattern, size)
                b.ResetTimer()
                for i := 0; i < b.N; i++ {
                    arr := make([]int, len(data))
                    copy(arr, data)
                    sort.Ints(arr)
                }
            })
        }
    }
}

4.2 典型结果

数据模式	10万元素耗时	胜出算法
完全随机	6ms	pdqsort (快排基因)
已排序	0.5ms	TimSort (直接识别)
逆序	0.5ms	TimSort (翻转)
部分有序	2ms	TimSort
大量重复	2ms	pdqsort (三向分区)

五、工程启示

5.1 没有银弹

1
2
3
4
5
// 需要稳定排序？
sort.SliceStable(data, less)  // 用 TimSort 思想的稳定排序

// 极致性能？
sort.Slice(data, less)  // 用 pdqsort

5.2 自定义排序的注意事项

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// 错误：比较函数不一致
sort.Slice(users, func(i, j int) bool {
    return users[i].Name <= users[j].Name  // <= 而不是 <
})
// 可能导致无限循环！

// 正确
sort.Slice(users, func(i, j int) bool {
    return users[i].Name < users[j].Name
})

5.3 何时写自己的排序？

几乎永远不要。标准库已经是最优解。

例外情况：

超大规模分布式排序 (MapReduce)
特定硬件优化 (GPU 排序)
外部排序 (磁盘归并)

六、总结

算法	设计理念	适用场景
TimSort	利用已有序列	Python/Java 对象排序
pdqsort	防御最坏情况	Go/Rust 高性能场景
IntroSort	快排 + 堆排混合	C++ STL

核心收获：

真实数据往往部分有序，TimSort 利用这一点
恶意输入可以攻击快排，pdqsort 检测并防御
小数组用插入排序，这是所有实现的共识
工程优化远比算法选择重要

目录