案例库 · 工程与运营 · 技术决策 · 2002-2003
Timsort利用数据中已有的顺序对现实世界数据进行排序
Tim Peters围绕自然连续段构建了Python的排序，将实际列表上的比较次数降至接近N——Java、Android和V8都采用了它。
Python软件基金会
那一手
排序算法通常以随机数据衡量性能，但实际列表很少是随机的——数据库、用户界面和日志通常以近乎有序的块形式出现。Python核心开发者Tim Peters在2002年为Python 2.3设计timsort时，正是基于这一观察：一种自适应、稳定、自然的归并排序，它发现数据中已存在的有序连续段并加以利用。
该算法从左到右遍历数组一次，识别升序或降序连续段；每个连续段被推入栈中，并在满足大小平衡条件时进行合并，以保证合并成本低廉。短于最小长度的连续段使用插入排序扩展，而插入排序在小型数组上速度较快。由于输入从不被盲目分割，部分有序的数据可以仅用N-1次比较完成排序。
这一算法取代了Python之前的samplesort混合算法，并自Python 2.3起作为标准list.sort()方法发布。它在真实数据上的实际速度使其得以输出：Java SE 7将其用于对对象数组进行排序，Android和GNU Octave也采用它，V8 JavaScript引擎也采用了它，Swift的排序和Rust的标准库也基于同样的思想构建。
Timsort是稳定的——相等元素保持相对顺序——因此它支撑了多关键字排序，例如先按邮政编码再按姓名排序。即使是2015年在标准实现中发现的一个微妙错误，也在Python、Java和Android中得到修复，这证明了该算法的应用范围之广。
为什么管用
- 自然连续段意味着数据在排序开始前就完成了一部分工作
- 合并栈标准保持合并平衡且比较次数接近最优
- 对于短连续段，插入排序比归并排序更高效
- 稳定性使其适用于多关键字排序流程
可以搬走什么
根据实际输入做性能分析，而不是最坏情况：如果数据带有结构，利用这种结构的算法在实际工作负载上会胜过理论上最优的算法。
后来呢
Timsort一直是Python的默认排序，直到Python 3.11用Powersort替代，后者是合并策略更稳健的后继者，而Timsort至今仍用于Java、Android、V8和Swift。2015年的错误曾在某些大型输入上导致Java和Android崩溃，现已在整个生态系统中修复——这表明大量真实软件如今依赖一位工程师2002年的设计。
资料来源
发现哪里写错了？告诉我们。