TimSort:一个在标准函数库中广泛使用的排序算法

在计算机科学的领域，排序算法是每位学生必学的基础，而排序的需求是每位程序员在编程过程中都会遇到的。

在你轻松调用 .sort() 方法对数据进行排序时，是否曾好奇过，这个简单的方法背后使用的是哪种排序算法呢？

本文将带你走进 TimSort，一个在标准函数库中广泛使用的排序算法。

这个算法由工程师 Tim Peters 于 2001 年专为 Python 设计，并自 Python 2.3 版本起成为其默认排序算法。它的影响不止于此，Java、Android、GNU Octave、Chrome 的 V8 引擎、Swift 以及 Rust 等也纷纷采用了这一算法。

那么，是什么让 TimSort 在众多排序算法中独树一帜，赢得了如此广泛的应用和认可呢？

在本文中，我们将深入剖析 TimSort 的内部机制，揭示其背后的高效实现原理，让你领略这一算法的独特魅力。

小规模数据的高效处理：插入排序

TimSort 是一个结合了插入排序和归并排序的混合排序算法，特别适合处理真实世界的各种数据。

从这句定义中您可能会好奇，为什么 TimSort 选择了插入排序和归并排序？为什么说它适合处理真实世界的数据？

让我们首先探讨第一个问题，为什么插入排序成为了 TimSort 的关键组成部分。

尽管插入排序的理论时间复杂度为 O(n^2)，看似不及 O(nlogn) 的高效排序算法，但插入排序的实际效率却非常高效，尤其是在处理小规模数据集时。

这是因为插入排序只涉及两个简单操作：比较和移动。

通过比较，我们能够确定新元素的插入点；通过移动，我们为新元素的插入腾出空间。

视频 插入排序

关键在于，对于小数据集而言，n^2 与 nlogn 的差异并不显著，复杂度不占主导作用，此时每轮单元的操作数量才起到决定性因素。得益于其简洁的操作，插入排序在小规模数据集上的表现通常非常出色。

但究竟什么规模的数据集算是“小”呢？

以 Python 为例，当数据集大小小于 64 时，它会默认采用插入排序。而在 Java 中，这一界限则被设定在了 32。

插入排序的优化：二分插入排序

对于 TimSort 算法来说，传统插入排序也存在进一步提升性能的空间。

回顾一下，插入排序涉及的关键操作有两个：比较和移动。这其中，对于一个数组来说，移动的总次数是固定不变的，因此，我们可以尝试从减少比较的次数来优化。

在插入排序的执行过程中，数据被划分为已排序和未排序的两个部分。在已排序部分，我们寻找未排序部分下一个元素的插入位置时，常规做法是采用线性查找。

但 TimSort 采用了更高效的策略——二分查找法。利用二分查找在已排序部分寻找插入点，大幅减少了比较次数。

对小规模数据集而言，这种优化尤其有效，能显著提升排序的效率。

视频 二分查找插入位置

举个例子，如上面视频所示，在使用传统插入排序时，为将元素 2 插入正确位置，需要进行 5 次比较。而在二分插入排序中，这一过程可以缩减至仅需 2 次比较，从而显著提高排序效率。

TimSort 的工作原理

在详细了解了插入排序在 TimSort 中的作用之后，接下来我们可以进一步了解归并排序在 TimSort 中的应用。不过在这之前，我们需要知道 TimSort 的整体工作原理。

TimSort 的设计目标是最大限度地利用在绝大多数实际数据中已经存在的连续有序序列，这些被称为自然序列 natural run。

在算法的执行过程中，它遍历数据集，借助于这些自然序列，必要时将附近的元素添加进去，形成一个个的数据块 run，其中每个 run 中的元素都会进行排序。

随后，这些有序的 run 被堆叠在一个栈中，形成了算法处理过程的一个关键结构。

动图 run 堆叠

当一个新的 run 被识别并加入到栈中后，TimSort 会根据栈顶多个 run 的长度来判断，是否应该合并栈顶附近的 run。

这个过程将持续进行，直到所有数据都遍历完。

run 合并

遍历结束后，栈中剩余的所有 run 每次两两合并，直到最终形成一个完整有序的 run。

相比传统归并排序，合并预排序的 run 会大大减少了所需的比较次数，从而提升了整体的排序效率。

现在，你可能对 TimSort 算法的细节产生了许多疑问。run 是如何形成的？这些 run 是如何利用数据中已存在的自然序列？当 run 被加入到栈中后，依据什么规则来决定是否合并？……

不用担心，接下来我们将逐一解答这些问题，带你更深入地理解 TimSort 算法。

计算 minrun

在 TimSort 算法中，run 的生成非常关键，而这一过程的核心是确定 run 最小长度 minrun。这个长度的设定是为了在排序过程中达到两个关键目标：

确保 run 足够长，以便有效地利用归并排序；

避免 run 过于长，从而在合并时仍能保持高效。

实验研究表明，当 minrun 小于 8 时，第一条原则难以满足；而当 minrun 超过 256 时，第二条原则受到影响。

因此，最佳的 minrun 长度范围被确定在 32 到 64 之间。

这个范围与我们之前提到的插入排序中小规模数据集的长度范围非常接近，这并非巧合。事实上，Timsort 在生成 run 时也会利用到插入排序。

具体计算 minrun 的方法如下：

目标：选取一个 minrun 值，以使长度为 n 的数组被分割成约 n/minrun 个 runs，每个 run 包含大约 32 到 64 个元素。

计算方法：选择最接近 n/(2^k) 的 minrun 值，这里 k 是使 n/(2^k) 落在32至64之间的最大整数。然后设置 minrun 为 n/(2^k)。

例如，对于长度为 65 的数组，minrun 将设置为33，形成 2 个runs；对于长度为 165 的数组，minrun 设置为42，形成 4 个runs。

这个计算过程涉及到 (2^k)，可以通过位移操作高效实现：

defget_minrun(n): #用于记录在不断右移过程中，n的最低位上非零位的数量 r=0 whilen>=64: #检查n的最低位是否为1，若是，则设置r为1 r|=n&1 #向右移动一位，相当于n除以2 n>>=1 #返回n加上r，n是原始值的最高6位，r是表示过程中n是否有非零最低位的标志 returnn+r

这种方法不仅保证了 minrun 的有效性，而且利用了位运算的高效性，体现了 TimSort 设计的巧思。

run 的生成过程

在掌握了 minrun 的计算方法之后，我们现在可以探究 run 是如何生成的。

TimSort 的核心目标是充分利用数据中已存在的连续有序序列来生成 run，但这是如何实现的呢？

TimSort 的处理流程可分为以下几个关键步骤：

TimSort 开始扫描整个数组，寻找连续的升序或降序序列。

如果遇到升序部分，TimSort 会持续扫描直到升序结束。

如果遇到降序部分，TimSort 会继续扫描直到降序结束，并随后将这部分翻转成升序。

如果上述步骤识别的 run 未达到 minrun 长度，TimSort 会继续扩展这个 run，向数组后方遍历，纳入更多元素，直至达 minrun 长度。在这个阶段，新加入元素的顺序并不重要。

一旦扩展完成，这个扩展后的 run（无论其最初是否有序）都将通过插入排序进行排序，以确保其内部有序。

如果识别的 run 长度远超 minrun，对于这些较长的连续有序序列，TimSort 会保持其原始长度，不进行切割。这是因为较长的有序序列对于减少后续合并操作的复杂度非常有利。

对于这些超长的 run，通常无需进行额外排序，除非它们是降序，这时 TimSort 会先将其翻转成升序。

通过这些策略，TimSort 能够高效地生成一个有序的、长度至少为 minrun 的 run，为后续的归并排序过程奠定了坚实基础。

栈中 run 的合并规则

在 TimSort 算法中，每生成一个新的 run，它就会被加入到一个专门的栈中。

这时，TimSort 会对栈顶的三个 run（我们称它们为X、Y和Z）进行检查，以确保它们符合特定的合并规则：

|Z| > |Y| + |X|

|Y| > |X|

如果这些条件没有被满足，Y 就会与 X 或 Z 中较小的一个合并，并重新检查上述条件。当所有条件都满足时，可以在数据中继续遍历生成新的 run。

run 合并

这种独特的合并规则是为了实现什么目标呢？

在 TimSort 的合并规则下，最终保留在栈中的每个 run 的长度至少等于前两个 run 的总长度（由于满足|Z| > |Y| + |X| 和 |Y| > |X|的规则）。

这种设计意味着，随着时间的推移，栈中 run 的长度会逐渐增大，其增长方式类似于斐波那契数列。

这种增长模式的一个重要优势在于，它提供了一种有效的方式来平衡数据遍历完成之后 run 的合并操作，同时避免了过于频繁的合并。

在最理想情况下，这个栈从顶部到底部 run 的长度应该是[2,2,4,8,16,32,64,...]。这样，从栈顶到栈底的合并过程中，每次合并的两个 run 的长度都是相等的，形成了完美的合并。

栈中 run 最理想形态

通过这些巧妙的规则，TimSort 在保证合并操作近似均衡的同时，也确保了在追求均衡和简化合并决策之间的权衡。

正如 Tim Peters 所指出的，找到一种方式来维持栈中这两个规则，是一个极具智慧的折中选择。

合并过程中的空间开销

了解完 TimSort 的工作原理和 run 在栈中的合并规则之后，我们现在来看 TimSort 中的最后一个重要环节：如何高效地运用归并排序？

虽然传统的归并排序也拥有 O(nlogn) 的时间复杂度，但它并不是原地排序，并且需要额外的 O(n) 空间开销，这使得它并没有被广泛地运用。

当然，也有改良过的原地归并排序的实现，但它们的时间开销就会比较大。为了在效率和空间节约之间取得平衡，TimSort 采用了一种改进的归并排序，其空间开销远小于O(n)。

以一个具体例子来说明：假设我们有两个已排序的数组 [1, 2, 3, 6, 10] 和 [4, 5, 7, 9, 12, 14, 17]，目标是将它们合并。

在这个例子中，我们可以观察到：

第二个数组中的最小元素（4）需要插入到第一个数组的第四个位置以保持整体顺序，

第一个数组中的最大元素（10）需要插入到第二个数组的第五个位置。

因此，两个数组中的 [1, 2, 3] 和 [12, 14, 17] 已经位于它们的最终位置，无需移动。我们实际上需要合并的部分是 [6, 10] 和 [4, 5, 7, 9]。

在这种情况下，我们只需要创建一个大小为 2 的临时数组，将[6, 10]复制到其中，然后在原数组中将它们与[4, 5, 7, 9]合并。

动图 归并排序 优化合并过程

这个例子展示了从前往后的合并过程。同样，还有从后往前合并的情况：

动态图 归并排序 从后往前合并

与传统归并排序相比，TimSort 在这里采用的优化策略显著减少了元素移动的次数，缩短了运行时间，并大幅降低了临时空间的需求。

合并过程中的 galloping mode

在归并排序过程中，通常的做法是逐个比较两个数组中的元素，并将较小的元素依次放置到合适的位置。

然而，在某些情况下，这种方法可能涉及大量冗余的比较操作，尤其是当一个数组中的元素连续地胜出另一个数组时。

想象一下，如果我们有两个极端不平衡的数组：

A = [1, 2, 3, …, 9999, 10000]

B = [20000, 20001, …, 29999, 30000]

在这种情况下，为了确定 B 中元素的正确插入点，我们需要进行高达 10000 次的比较，这无疑是低效的。

如何解决这个问题呢？

TimSort 的解决方案是引入了所谓的“跃进模式”（galloping mode）。这种模式基于一个假设：如果一个数组中的元素连续胜出另一个数组中的元素，那么这种趋势可能会持续下去。

TimSort 会统计从一个数组连续选中的元素数量，一旦连续胜出次数达到了称为 min_gallop 的阈值时，TimSort 就会切换到跃进模式。

在这种模式下，算法将不再逐个比较元素，而是将实施一种指数级搜索（exponential search）。以指数级的步长（2^k）进行跳跃，首先检查位置 1 的元素，然后是位置 3 (1 + 2^1 )，接着是位置 7 (3 + 2^2)，以此类推。

当首次找到大于或等于比较元素的位置时，我们就将搜索范围缩小到上一步的位置（2^(k-1) + 1）和当前步的位置（2^k + 1）之间的区间。

在这个区间内进行更二分搜索，以快速定位正确的插入位置。

据开发者的基准测试，只有当一个数组的首元素并不处于另一数组的前 7 位置时，跃进模式才真正带来优势，因此 min_gallop 的阈值为 7。

上面的步骤看起来比较复杂，我们以两个数组为例：

A = [1, 25, 31, 37]

B = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36]

根据之前合并过程中的空间开销原则，A 中的元素 1 是固定的，此时将25, 31, 37 移动到临时空间进行合并排序。

动图 跃进模式 1

在这种情况下，当 25 在与 B 数组元素比较时连续胜出，触发了跃进模式。

动图 跃进模式 2

算法直接跳跃到位置 15 (7 + 2^3)，发现 30 大于 25。

动图 跃进模式 3

进而在位置 7 和 15 之间执行二分搜索，以找到 25 的插入点。

动图 跃进模式 4

虽然跃进模式在某些情况下能极大提高效率，但它并非总是最优选择。有时，跃进模式可能导致更多的比较操作，尤其是在数据分布较为均匀时。

为了避免这种情况，TimSort采用了两种策略：一是当识别到跃进模式的效率不及二分搜索时，会退出跃进模式；二是根据跃进模式的成功与否调整 min_gallop 值。

如果跃进模式成功且连续选择的元素均来自同一数组，min_gallop 值会减 1，以鼓励再次使用跃进模式；反之，则加 1，减少再次使用跃进模式的可能性。

结语：TimSort - 数据排序的实用革新

在探索数据排序这个历史悠久且充满挑战的领域中，TimSort 算法不仅是一项威廉希尔官方网站 成就，更是实用性与创新的杰出典范。它的出现，不单单是算法领域的一个新节点，更是对现实世界复杂数据处理需求的有效回应。

TimSort 的真正魅力不仅在于它的高效率，更在于它对实际数据特性的深入理解和利用。这个算法不是静态的，它通过对数据的观察，动态调整自身策略，以适应不同的数据模式。

这种设计思路提供了一个重要的启示：在面对现实世界问题时，理论和实践的结合往往比单纯追求理论完美更为重要。

通过本文的深入分析，我们对 TimSort 的工作原理及其核心概念有了更为直观的理解。现在，如果再次回顾它的定义，您会发现自己有了更深刻的认识。

参考资料：

[1] https://en.wikipedia.org/wiki/Timsort

[2] https://dev.to/brandonskerritt/timsort-the-fastest-sorting-algorithm-you-ve-never-heard-of-2ake

[3] https://www.infopulse.com/blog/timsort-sorting-algorithm

[4] https://juejin.cn/post/6844904131518267400

[5] https://www.youtube.com/watch?v=_dlzWEJoU7I

[6] https://www.youtube.com/watch?v=1wAOy88WxmY