2026 年 11 月 11 日,Guido van Rossum 在 Python 官方开发者论坛发帖,宣布 Tim Peters 已于今年 7 月 15 日去世,帖名《In Memoriam: Tim Peters 1952–2026》。消息传出后,Hacker News 上的讨论帖冲到 1200 分以上、134 条评论,Lobsters 与 r/Python 同步出现悼念帖。Python 官方论坛那篇讣告发出一天,浏览量 6.9 万次、599 个赞,29 位开发者参与回帖。

Guido 在讣告里给了他一个很少见于官方表述的身份定位:mentor and language co-designer(导师和语言的共同设计者)。Tim 在 Python 发布初期就成为用户,他做的第一件事是说服 Guido 让 Python 支持 int 和 float 的混合算术,因为大多数用户会默认它们就该那样工作。此后三十年,从语言设计讨论到邮件列表答疑,他没有停下来过。
一份写在源码树里的排序设计文档
讣告之外,Tim Peters 留下的最硬的工程遗产是 Timsort。2002 年他为 Python 列表设计了这套排序算法,Python 2.3 起成为 list.sort 的实现。设计说明至今放在 CPython 源码树的 Objects/listsort.txt 里,开头第一句是:
This describes an adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it <wink>).
括号里那个 <wink> 是他的签名式幽默,后文再谈。算法本体是一次从左到右的单趟扫描:先识别数组里天然存在的连续有序段(run),再把它们按一套规则逐个合并。短于 minrun 的 run 用稳定的二分插入排序补齐,minrun 取 32 到 64 之间、尽量是 2 的幂,让后续合并接近完全平衡。合并时如果发现某一边持续占优,算法切入 galloping 模式,用指数跳跃式探测(B[0]、B[1]、B[3]、B[7]……)一次搬走一整段,而不是一对一对比较。

这份文档给出的性能边界写在开头:对部分有序的数组,比较次数可以低于 lg(N!),最好情况少到 N-1;随机数组上的速度则与之前高度调优的 samplesort 持平。Tim 用四个小时随机数组实验做对照,samplesort 多花了约 1.5% 的比较次数。内存上它最多需要容纳 N/2 个指针的临时数组,数据结构性强的时候可以完全不占额外堆内存。
这份文档本身也还在生长。2025 年,Stefan Pochmann 找到了更好的 minrun 选择方案(让 minrun 在不同 run 之间轻微浮动,使合并树的每一层 run 数都接近 2 的幂),文档随即跟着更新。二十多年过去,CPython 的排序文档仍在接收算法层的修订。
从 CPython 搬进 Java、Android 和 V8
Timsort 的传播路径在排序算法里几乎独一无二。按照欧盟 ERCIM 新闻的估算,使用这套算法的电脑、云服务和手机数量在数十亿台量级。具体去向包括:
- Java 标准库:java.util.Arrays.sort 与 Collections.sort 的对象排序路径,即 java.util.TimSort
- Android:平台文档中直接以 java.util.TimSort 类名出现
- V8:v7.0 / Chrome 70 起,Array.prototype.sort 从 Quicksort 换成用 Torque 语言实现的 Timsort,JavaScript 的排序从此稳定
- GNU Octave:排序实现 oct-sort.cc 的注释写着「代码大部分取自 Python 的 listobject.c,感谢 Tim Peters 让我抄袭(ripped-off)这些部分」
一份为 CPython 列表写的算法,最终成为三大陆主流运行时的默认排序,这在开源史上没有几个先例。
2015 年,形式化验证在 Timsort 里抓出一个 bug
2013 年,荷兰 CWI 的形式化方法组联合莱顿大学和达姆施塔特工业大学,想用验证工具 KeY 证明 TimSort 的正确性。结果证不出来,团队仔细一查,算法里确实有 bug,而且 Python 的 C 实现同样中招。
问题出在合并策略的栈管理上。run 的长度被压进一个数组,每次压栈后,mergeCollapse 检查栈顶三个 run 是否满足不变量:
runLen[n-2] > runLen[n-1] + runLen[n]
这条式子让 run 长度按斐波那契式的节奏指数增长,栈深被压在很小的量级,runLen 数组只需固定大小。Java 实现按 int 上限 2^31−1 给它分了 40 格。但 CWI 团队证明:只检查栈顶三个 run,并不足以让整条栈都满足不变量,破坏可以从更深处积累。他们构造出长度 67,108,864(2^26)的输入,让当时的 OpenJDK 实现当场抛出 ArrayIndexOutOfBoundsException: 40,出错点在 pushRun。论文还顺带算出 39 格其实是安全下界,40 格纯属运气好。
修复方案是把检查范围从最后三个 run 扩大到最后四个 run。团队用 KeY 对修复版做了机械验证:超过 200 万条推理规则、数千次人工干预,ERCIM 的总结称这是「对现存 Java 库做过的最难的正确性证明之一」。2015 年 2 月 bug 报告提交后,Python 率先打上对应补丁,Java 各发行版随后跟进。一场始于「想证明它对」的学术尝试,最后变成所有主流运行时的一次同步修复。
Python 3.11 的接棒者
2022 年发布的 Python 3.11 里,list.sort 的合并顺序策略换成了 J. Ian Munro 与 Sebastian Wild 设计的 Powersort(CPython 改动单 bpo-34561),Timsort 的原始合并策略正式退役。整体框架没有变:依然是那套识别 run、按栈规则合并的自适应稳定归并,换的是「多个待合并 run 之间先合并哪两个」的排序依据。Powersort 后来也被 NumPy、PyPy 和 WebKit 采用。
从 2002 年的设计文档到 2022 年的策略替换,再到 2025 年的 minrun 修订,这套算法的骨架与策略一直在分开演化,而每一环的演化记录都写在同一份 listsort.txt 里。
19 条格言与一个没填的空位
比起 Timsort,更多人第一次接触 Tim Peters 的名字是在解释器里敲下 import this 的瞬间。1999 年 6 月,他在 comp.lang.python 的一个讨论串里贴出 20 条 Python 设计格言,只写下了 19 条,第 20 条他说留给 Guido 来填。这个空位至今没有被填上:2004 年 8 月这组格言正式编号为 PEP 20,进入公共领域,Abstract 一栏明确写着「20 条格言,只写下了 19 条」。
彩蛋的实现也带着他的趣味:标准库 Lib/this.py 的源码里存的是一段 ROT13 编码的字符串,明文要等解释器执行时现场解码打印,第一行是 Gur Mra bs Clguba, ol Gvz Crgref。Hacker News 讨论帖里被顶在最高处的评论之一,就是完整贴出 import this 的输出,下面的跟帖接着贴出 this.py 里那段 ROT13 原文,一问一答之间把这个彩蛋拆开给所有人看。

Timbot 的二十年
在邮件列表时代,Tim Peters 的影响力由另一种东西构成。Guido 的讣告里写道,他凭借无数、仔细且耐心的答疑赢得了 Timbot 这个绰号,答案里永远带着轻度幽默,落款固定是 <wink> 或 <0.5 wink>,社区把他的发言称作「channeling Guido」(通灵 Guido)。Chris McDonough 在悼念帖里回忆,Tim 和 Guido 在很大程度上是早期 Python 设计演进的搭档,绝大多数重要特性进语言之前,都被两个人从每个角度摇晃、搅拌、反复琢磨过。
他的产出清单远不止排序和格言:标准库的 doctest 和 timeit 模块出自他手;《Python Cookbook》第一版的他负责算法章节,第二版封面上那句 We read Knuth so you don't have to(我们替你读了 Knuth)被他视为己任;他与 Gary Robinson 把 Paul Graham 的《A Plan for Spam》落地成开源反垃圾邮件系统 SpamBayes,Robinson 本人在纪念帖下确认这段合作,还提到自己最近让 AI 写同功能代码,模型输出的几乎就是 Tim 当年的实现。

组织层面,他在 2001 到 2014 年间担任 Python 软件基金会理事,2017 年获 PSF 杰出服务奖。Stack Overflow 上他的声望值停在 71,610。职业生涯早期,他在 Cray Research 写超算编译器,在 Dragon Systems 做当时被认为近乎不可能的语音转文字,1991 年起在 Kendall Square Research 工作,后来还去过 Harley-Davidson。2022 年 1 月,他还在 CPython 议题追踪器里开了 issue 90716,指出大整数与字符串互转的二次方复杂度问题,并附上自己的原型脚本。
收在文档上
悼念帖里,CPython 核心开发者 Petr Viktorin 写道:他大学毕业、满脑子教科书算法的时候读了 Objects/listsort.txt,惊讶于一份源码树里的文档能同时装下那样的深度、严谨、常识和人情味。Guido 那篇讣告的落款,则套用了 Tim 招牌的签名句式:Python-would-not-be-what-it-is-today-without-Tim-ly y'rs。
来源:discuss.python.org 讣告 · CPython Objects/listsort.txt · ERCIM News: Fixing the Sorting Algorithm for Android, Java and Python · de Gouw et al., OpenJDK's java.utils.Collection.sort() is broken (PDF) · PEP 20 · V8 blog: Array.prototype.sort · Powersort in Python 3.11 · Wikipedia: Tim Peters