Timsort 是一种稳定、自适应的排序算法,由蒂姆·彼得斯(Tim Peters)于 2002 年为 Python编程语言开发。它将归并排序与插入排序结合起来,识别输入序列中已有序的部分,并高效地将它们合并。其最坏情况运行时间为 ,而对于已有序的输入,处理时间可达 。Timsort 通过编程语言库的采用产生了广泛影响,尤其适用于对象序列的排序:在这类场景中,保持相等元素的原有顺序,以及减少代价高昂的比较,都十分重要。
设计与性质
Timsort 是一种基于比较的算法:它通过比较来确定顺序,而不是检查排序键的内部表示。它主要面向数组(数据结构)及支持高效索引访问的类数组序列。
其设计有三个显著特点:
- **稳定性:**排序键相等的元素保持原有的相对顺序。
- **自适应性:**利用输入中已有的顺序,而不是将所有输入都视为任意排列。
- **混合构造:**用插入排序处理短序列,再通过归并组合较长的有序序列。
当记录需要按不同字段反复排序时,稳定性很有用。例如,先按姓名对员工记录排序,再按部门进行稳定排序,所得记录会按部门分组,而各组内部仍保持姓名的字母顺序。
Timsort 通常不会为整个结果另建一个输出数组,但在归并过程中需要临时存储空间。因此,按照仅允许使用常数辅助空间的严格定义,它不属于原地排序算法。
自然有序段
Timsort 的核心单位是有序段(run),即一段已经有序的连续子序列。
自然升序段是非递减的:
降序段可以通过反转变为升序段。在经典算法中,降序段必须严格递减:
严格不等关系用于保障稳定性。如果降序序列中含有排序键相等的元素,反转就会颠倒它们的相对顺序。实现可以识别包含相等元素的更复杂模式,但必须采取措施抵消这种影响。
例如,序列
包含三个自然有序段:
反转第二段后,就得到三个可以归并的升序段。
有序段检测使 Timsort 特别适合处理以下数据:由多个已排序批次拼接而成的数据、时间戳字段基本有序的记录,以及自上次排序后仅经过少量编辑的序列。完全升序的输入本身就是一个有序段;完全严格降序的输入在反转后也会成为一个升序段。
扩展短有序段
过短的有序段会导致大量小规模归并,并带来过多的管理开销。因此,Timsort 会选定一个有序段长度的最低目标值,通常称为 minrun。
当自然有序段短于这个目标值时,算法会用二分插入排序将其扩展。已有序的部分充当初始有序前缀;每个新增元素的插入位置通过二分查找确定,随后移动中间的元素,为插入腾出空间。
二分查找减少了定位插入位置所需的比较次数,但每次插入时,移动元素仍可能需要线性工作量。由于需要扩展的有序段被有意限制得很短,这种开销是可以接受的。
按照 Python 经典实现的计算方法,元素数量至少为 64 的输入,其 minrun 在 32 到 64 之间,包含两端。更小的输入可以直接用插入排序处理为一个有序段。其他实现可能采用不同的阈值。
该计算方法还力求让最终得到的有序段数量接近二的幂。这样有利于形成较为均衡的归并过程,避免最后留下一个很大的有序段与一个小得多的剩余段进行归并。
例如,按照经典计算方法,2,112 个元素对应的 minrun 为 33。如果自然有序段都不超过这个长度,就会得到 64 个等长的有序段,从而形成均衡的归并结构。
管理归并顺序
发现有序段只是算法的一部分。归并顺序会显著影响数据移动的总量。
如果不断将许多小段并入一个逐渐增大的累积段,同一批元素就可能被反复复制。Timsort 则将待归并的有序段保存在一个栈(数据类型)中,并应用相应规则,使各段的大小保持适当的均衡。
经典栈不变量
对经典 Timsort 的一种常见描述,使用三个连续有序段的长度 、 和 ,按从较早发现到较晚发现的顺序排列,并要求满足:
当相关条件被违反时,就合并相邻的有序段。实现会根据各段的长度,选择合并哪一对相邻段。
在整个待归并栈中维持相应条件,可以使有序段长度朝栈底方向迅速增长。这将待归并段的数量限制在对数级别,并有助于控制归并成本。
这些不等式描述的是基本思路,而非完整的实现步骤。正确决定需要向栈的深处检查到什么位置至关重要。在某些实现中,仅检查最新的三个有序段并不足够。
扫描完全部输入后,继续归并剩余的待归并段,直到只剩下一个有序段。归并仅发生在相邻段之间,从而保持排序键相等的元素原有的从左到右顺序。
基于 Powersort 的调度
有序段发现、短段扩展、归并以及归并调度是可以分离的组件。库可以保留 Timsort 的大部分机制,同时替换原有的栈策略。
Powersort 利用有序段的位置和长度信息来选择归并操作,以近似构建高效的有序归并树。Python 从 3.11 版起采用了基于 Powersort 的归并策略,同时保留了 Timsort 的整体框架。
因此,描述 Python 排序时,需要区分经典 Timsort 的归并策略与较新 Python 版本使用的策略。
归并与疾驰
临时存储
在合并两个有序段之前,Timsort 可以排除那些已经确定处于正确位置的部分。例如,左段开头的一部分可能小于右段的所有元素,因此无需移动。
算法通常会将排除上述部分后剩余的较短段复制到临时缓冲区:
- 如果左段较短,就从前向后归并。
- 如果右段较短,就从后向前归并。
选择归并方向是为了避免覆盖尚未读取的元素。处理相等元素时,也必须采用与归并方向相匹配的规则,才能保持稳定性。
最坏情况下,临时存储空间需要容纳约一半的输入元素。对于对象引用数组,这通常意味着存储引用,而不是复制对象本身。
疾驰模式
普通归并会反复比较两个有序段各自的下一个候选元素。当连续多个元素都来自同一段时,Timsort 可能切换到疾驰(galloping)模式。
疾驰先以指数增长的步长进行探测,确定一个范围,再通过二分查找找出其中的边界。随后便可整块复制元素,而不必将其中的每个元素分别与另一段的候选元素进行比较。
例如,假设某一段的下一个元素是 100,而另一段开头有一长串小于 100 的值。与逐个元素归并相比,疾驰可以用少得多的比较次数找到这串元素的末尾。
疾驰并不能省去复制整块元素的工作。它的主要好处是减少比较次数及相关的控制开销。由于两个有序段的元素频繁交替出现时,疾驰反而可能降低效率,Timsort 会根据这一技巧的实际效果调整进入疾驰模式的阈值。
复杂度与性能
对于正确实现、且归并策略能够提供预期保证的算法,其主要界限如下:
| 性质 | 界限或行为 |
|---|---|
| 最佳情况运行时间 | |
| 最坏情况运行时间 | |
| 最坏情况辅助存储空间 | |
| 待归并段栈的空间 | |
| 稳定性 | 保持 |
| 自适应性 | 利用已有的有序段 |
这些时间复杂度界限假定比较和元素移动都只需常数时间。复杂对象、长字符串或用户自定义值之间的比较,本身就可能有相当大的开销。
与仅看最坏情况界限相比,自适应性更能说明算法的表现。如果输入由少量较长的有序段组成,所需工作量可能远小于同等规模的高度无序输入。不过,有序段的数量并非唯一相关因素:各段的长度、排列方式,以及取值范围之间的重叠程度,也会影响性能。
算法的空间复杂度是一项实际限制。对于内存限制严格的应用,即使需要牺牲稳定性或自适应性,也可能更倾向于选择辅助存储需求更小的算法。
历史与应用
蒂姆·彼得斯在 Python 2.3 中引入了 Timsort,取代了此前的排序实现。其设计注重实际数据中常见的模式,而不只是均匀随机排列。
Java编程语言从 Java 7 起采用 Timsort 对对象数组进行排序。这并不意味着 Java 的所有排序操作都使用它:基本类型数组的排序使用过不同的算法,并行排序也有单独的实现策略。
Timsort 也成为形式验证研究中的一个重要案例。2015 年报告的一项研究发现,广泛使用的实现中,关于待归并段栈大小上界的推理存在缺陷。特意构造的有序段序列可能超出固定大小栈所假定的容量。
这是实现和不变量维护方面的问题,并不说明稳定的自然归并方法本身不可靠。不同实现通过调整栈容量、修改触发归并的规则,或同时采用这两种方式来解决问题。这一事件表明,只有代码确实维持了一个直觉上似乎合理的循环不变量,基于它推导出的结论才成立。
与其他排序算法的比较
与传统归并排序相比,Timsort 增加了自然有序段检测、短段扩展、疾驰以及自适应归并调度。两者都可以提供稳定性和 的最坏情况时间保证,但 Timsort 能从已有顺序中获得更大的收益。
与快速排序相比,Timsort 既保持稳定性,又无需依赖枢轴选择即可保证 的最坏情况时间。快速排序的实现通常使用更少的辅助内存,并且对于某些数据类型或工作负载可能更快。其确切保证取决于具体变体。
与堆排序相比,Timsort 使用更多辅助空间,但能保持排序键相等元素的顺序,并利用自然有序段。堆排序仅需常数辅助存储空间,就能提供 的最坏情况时间界限,但通常不稳定。
与单独使用插入排序相比,Timsort 保留了插入排序在短序列或近乎有序序列上的优势,同时避免了对整个输入排序时出现平方级的最坏情况时间。
局限与实现要求
Timsort 的各项保证依赖于一致的比较关系。如果比较函数违反了顺序关系的要求,例如对相同元素给出相互矛盾的结果,就可能使有序段检测和归并所依据的假设失效。
正确实现 Timsort 比实现基本归并排序复杂得多。重要细节包括:
- 在有序段反转、插入以及两个方向的归并中保持稳定性;
- 维持待归并段所需的全部条件;
- 一致地处理疾驰边界和相等的排序键;
- 安全地确定临时存储空间和栈结构的容量;
- 避免无效的索引计算和整数溢出。
其性能优势取决于工作负载。如果输入几乎没有可利用的顺序、比较成本很低,或内存限制极其严格,其他算法可能更合适。Timsort 尤其适用于这样的通用稳定排序场景:数据中经常存在已有顺序,而比较操作的成本未必低廉。