OI-wiki 基础算法篇：Timsort 混合稳定排序算法深度解析-育师

OI-wiki 基础算法篇：Timsort 混合稳定排序算法深度解析

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读

Timsort 是一种由 Python 核心开发者 Tim Peters 于 2002 年设计的混合稳定排序算法，它巧妙结合了插入排序与归并排序的优点，针对数据集中天然存在的"部分有序"特性进行了精确优化，因而特别适合处理包含大量有序子序列的真实数据。本文以 docs/basic/tim-sort.md 为主体，结合仓库中插入排序、归并排序与排序算法总览等相邻章节，系统讲解 Timsort 的 Run 识别、Run 扩展、栈式归并与加速模式等核心机制，并给出完整的复杂度证明与伪代码实现，帮助读者理解 Python、Java 等语言默认排序背后的工作原理。

引入：为什么需要 Timsort

在 Timsort 出现之前，常见的排序算法各有短板：快速排序在部分有序数据上容易退化，插入排序对小规模数据高效但整体复杂度为 $O(n^2)$，归并排序稳定但常数较大。Timsort 的设计初衷，就是识别并利用数据集中已有的有序性——真实世界中的数据（如日志记录、用户列表）往往并非完全随机，而是包含大量已排序的连续片段。

Timsort 由 Python 核心开发者 Tim Peters 于 2002 年设计并应用于 Python 语言，自 Python 2.3 版本起被选为 Python 标准库的默认排序算法，此后也被广泛应用于其他编程环境，例如在 Java SE 7 中用于对非原始对象数组进行排序。

从仓库的排序章节结构看，Timsort 属于"基于比较的稳定排序"家族。正如排序算法总览所述，稳定性是指"相等的元素经过排序之后相对顺序是否发生了改变"，而归并排序、插入排序均属稳定排序——Timsort 正是以这两者为基石的混合体。仓库基础算法目录也将本章内容定位为"足够优美及趣味性，在之后的进阶内容中也常常会出现"的基础算法。

算法总流程：识别、扩展、归并三步走

Timsort 的核心思想是通过识别和利用数据集中已有的有序性来提高排序效率，其主要包括以下步骤：

识别 Run：扫描待排序数组，识别出有序的连续子序列（Run）。
扩展 Run：如果识别的 Run 长度小于MIN_RUN，则使用插入排序对其进行扩展。
归并 Run：Timsort 维护一个特殊的栈，采用特定的归并策略将栈中已有的 Run 合并成更大的有序序列。

识别 Run

首先，Timsort 会从左向右扫描数组，识别出连续的有序序列，这些有序序列被称为 Run：

升序 Run：如果后一个元素大于等于前一个元素，则继续扩展 Run。
降序 Run：如果后一个元素小于前一个元素，则继续扩展 Run，随后将该 Run 反转为升序。

这里值得注意两点：其一，升序 Run 判定使用的是"大于等于"，即允许相邻相等元素共存于同一 Run，这与归并排序中为保证稳定性而采用a[i] <= b[j]而非a[i] < b[j]的取舍一脉相承；其二，降序 Run 会被整体反转，使得栈中保存的 Run 一律为升序，从而统一后续归并的处理逻辑。

扩展 Run：二分插入排序补齐到 MIN_RUN

为了提高小规模数据的排序效率，Timsort 引入了一个 Run 的最小长度MIN_RUN。其值一般根据待排序数组的长度动态计算，通常为 $32$ 至 $64$ 之间。

如果识别的 Run 长度大于等于MIN_RUN，则不需要额外操作，直接将 Run 压入栈中。
如果识别的 Run 长度小于MIN_RUN，则使用二分插入排序将该 Run 的后续元素插入到 Run 中，直到 Run 的长度达到MIN_RUN，然后将其压入栈中。

"二分插入排序"正是仓库插入排序中"折半插入排序"一节所述的技术：通过二分查找（仓库中使用upper_bound）确定插入位置后，再用memmove批量移动元素。折半插入排序与直接插入排序的基本思想一致，只是对常数进行了优化，时间复杂度不变——这正是 Timsort 在大规模排序中使用它的理由：扩展 Run 的长度被限制在MIN_RUN（不超过 64），此时 $O(k^2)$ 的插入排序在常数很小的前提下完全可控，且相比归并操作开销更低。

归并 Run：用栈管理平衡的归并

在 Timsort 中，归并排序是通过栈来管理和控制的。栈中保存了已经识别出的有序 Run，并通过特定的归并规则控制栈中 Run 的合并，其目的是在合并时保持序列的平衡性和稳定性。

归并规则：稳定性与平衡性双保证

Timsort 是一种稳定的排序算法，即相同元素在排序后仍然保持原有的相对顺序。为确保这一点，Timsort 在归并时只会合并相邻的、连续的 Run，而不会直接合并非相邻的 Run——因为非相邻的 Run 之间可能存在相同的元素，直接合并很可能会打乱它们的相对顺序。

同时，为了确保合并的平衡性，Timsort 引入了特定的归并规则。在每次合并操作之前，算法会检查栈顶的三个 Run X、Y 和 Z，以确保满足以下两个条件：

条件一：len(Z) > len(Y) + len(X)
条件二：len(Y) > len(X)

如果栈顶的三个 Run 不满足上述条件，Timsort 会将 Y 与 X 或 Z 中较小的一个进行合并，然后再次检查条件。一旦条件满足，则开始继续搜索新的 Run，将其添加到栈中并开始下一轮的归并。

这两个条件可以直观理解为：栈中 Run 的长度自底向上大致呈非严格递减，且任意三层都满足"下层能包住上层之和"。这保证了合并是延迟的、按需的——只有出现长度失衡时才触发合并，从而让各次归并的代价保持均衡，避免出现某次归并一方 Run 极小、另一方极大导致的低效。

归并优化：二分定位 + 临时缓冲区

为了在归并不同长度的 Run 时提高效率并减少空间开销，Timsort 在归并前会通过二分查找精确定位需要处理的元素范围，只对需要移动的部分进行归并，具体方式为：

确定插入点：使用二分查找，找到第二个 Run 的第一个元素在第一个 Run 中的插入位置，以及第一个 Run 的最后一个元素在第二个 Run 中的插入位置。这样，可以缩小需要归并的范围，只对需要移动的元素进行处理。
临时缓冲区：传统的原地合并算法效率太低，需要大量的元素移动。为了减少这种开销，Timsort 使用一个临时缓冲区，将长度较小的 Run 复制到缓冲区中，然后逐步将元素从缓冲区复制回原数组。

例如，假设存在两个 Run A 和 B，分别为：

Run A：$[1, 2, 3, 6, 10]$
Run B：$[4, 5, 7, 9, 12, 14, 17]$

通过二分查找，可以确定：

元素 $4$ 应插入到 Run A 的第四个位置；
元素 $10$ 应插入到 Run B 的第五个位置。

因此，Run A 的前 $3$ 个元素和 Run B 的后 $3$ 个元素已经在正确位置，无需处理。只需归并 Run A 的 $[6, 10]$ 和 Run B 的 $[4, 5, 7, 9]$，其归并过程如下图所示：

从示意图可以看到，归并时只需把较小的 Run（即数据较少的 $[6, 10]$）复制进"临时内存"缓冲区，随后将另一侧的元素依次归并回原数组——这与归并排序中"使用与原数组等长的辅助数组"的经典做法相比，显著减少了辅助空间与移动开销。

加速模式：Galloping Mode 与动态阈值

为进一步提升归并效率，Timsort 引入了加速模式（Galloping Mode）。在标准的归并过程中，算法会逐一比较两个 Run 中的元素，将较小的元素放入结果数组。然而，如果一侧的 Run 中有大量连续元素比另一侧的当前元素要小，逐一比较会造成不必要的开销。

为了解决这一问题，Timsort 设定了一个阈值Min_Gallop（默认值为 $7$）。当一侧 Run 中的元素连续比较胜利的次数达到Min_Gallop时，算法会进入加速模式，快速定位元素位置，其具体步骤如下：

指数查找：从当前位置开始，算法以指数增长的步长 $(1, 2, 4, 8, \dots)$ 在一侧的 Run 中查找，直到找到一个区间，使得目标元素位于该区间内。
二分查找：一旦确定了包含目标元素的区间，算法会在该区间内使用二分查找，精确定位目标元素的位置。

通过这种方式，Timsort 可以跳过大量不必要的比较，快速处理一侧 Run 中连续的、较小（或较大）的元素，将它们批量移动到合并结果中。

然而，加速模式并非在所有情况下都更高效。在某些数据分布下，加速模式可能导致更多的比较次数。为此，Timsort 采用了动态调整策略：

阈值调整：维护一个可变的Min_Gallop参数。当加速模式表现良好（即连续多次从同一 Run 中选取元素）时，Min_Gallop减 $1$，鼓励继续使用加速模式；当加速模式效果不佳（频繁在两个 Run 之间切换）时，Min_Gallop加 $1$，降低加速模式的使用频率。

通过动态调整Min_Gallop的值，算法能够根据实际数据情况，在普通归并模式和加速模式之间取得平衡。对于部分有序或高度有序的数据，加速模式可以显著提高效率，使 Timsort 的性能接近 $O(n)$；而对于随机数据，算法会逐渐倾向于使用普通归并，从而保证 $O(n \log n)$ 的时间复杂度。

复杂度分析

Timsort 的时间复杂度取决于数据的有序性：

最优情况：$O(n)$——当数据已经有序或近似有序时，算法识别出的 Run 长度接近 $n$，归并次数减少，复杂度趋近于 $O(n)$。
最坏情况：$O(n \log n)$——在数据完全无序的情况下，每一个 Run 的长度都接近 $1$，因此需要 $O(\log n)$ 次归并，每次归并的代价为 $O(n)$，总复杂度为 $O(n \log n)$。

证明：

识别和扩展 Run：
- 识别 Run 需线性遍历一次数组，其复杂度为 $O(n)$。
- 使用插入排序扩展 Run 也需线性遍历数组，其复杂度为 $O(n)$。
归并 Run：
- 归并操作的总次数与 Run 的总数有关，最坏情况下 Run 的数量为 $n / \text{MIN_RUN}$，由于MIN_RUN是常数，因此 Run 的数量可看作 $O(n)$。
- $O(n)$ 个 Run 需要进行的归并次数为 $O(\log n)$，每次归并操作的代价为 $O(n)$，因此归并操作的总复杂度为 $O(n \log n)$。

而对于空间复杂度，由于 Timsort 大致需要额外的 $O(n)$ 空间用于存储栈和临时缓冲区，因此总的空间复杂度为 $O(n)$。作为对照，排序算法总览指出"基于比较的排序算法的时间复杂度下限是 $O(n\log n)$"——Timsort 的最坏情况恰好达到了这一理论下界，同时又在最优情况下突破到线性，这正是其"自适应"价值的体现。

实现：伪代码全流程

以下伪代码完整展示了 Timsort 的主循环逻辑（摘自 docs/basic/tim-sort.md）：

$$ \begin{array}{ll} 1 & nRemaining \gets \text{数组长度} \ 2 & minRun \gets \text{选择合适的 MinRun 的值}(nRemaining) \ 3 & startIndex \gets 0 \ 4 & \textbf{while } nRemaining > 0 \ \textbf{do} \ 5 & \qquad runLength \gets \text{识别 Run }(array, startIndex, nRemaining) \ 6 & \qquad \textbf{if } runLength < minRun \ \textbf{then} \ 7 & \qquad \qquad extendLength \gets \min(minRun, nRemaining) \ 8 & \qquad \qquad \text{使用插入排序扩展区间 } [startIndex, startIndex + extendLength - 1]\ 9 & \qquad \qquad runLength \gets extendLength \ 10 & \qquad \textbf{end if} \ 11 & \qquad \text{将 Run } (startIndex, runLength) \text{ 压入栈中} \ 12 & \qquad \textbf{调用 } \text{mergeCollapse(栈)} \ \text{检查并合并栈中的 Run } \ 13 & \qquad startIndex \gets startIndex + runLength \ \text{更新起始位置} \ 14 & \qquad nRemaining \gets nRemaining - runLength \ \text{更新剩余长度} \ 15 & \textbf{end while} \ 16 & \textbf{调用 } \text{mergeForceCollapse(栈)} \ \text{对栈中所有 Run 进行最终的合并} \ \end{array} $$

对照前文的机制讲解，可以逐一对应伪代码中的关键环节：

第 2 行根据剩余长度动态计算minRun（即MIN_RUN，通常取 $32 \sim 64$），对应"扩展 Run"一节；
第 5 行识别 Run，对应"识别 Run"一节（含降序反转）；
第 6～10 行在 Run 过短时用插入排序补齐到minRun；
第 11～12 行压栈并调用mergeCollapse，后者内部实现了"归并规则"一节的栈顶三元素检查与条件触发合并；
第 16 行在全部 Run 入栈后调用mergeForceCollapse做最终的强制归并，将所有 Run 合并为完整有序数组——此阶段的归并同样享受二分定位、临时缓冲区与加速模式三项优化。

总结与延伸阅读

Timsort 的成功在于三点设计上的"对症下药"：识别 Run把数据中已有的有序性直接转化为可复用资产；栈式归并规则（len(Z) > len(Y) + len(X)与len(Y) > len(X)）在保证稳定性的前提下维持归并的平衡性；加速模式与动态Min_Gallop则让算法在"批量跳跃"与"逐元素比较"之间自适应切换。三者叠加，使得 Timsort 在部分有序数据上逼近 $O(n)$，在随机数据上保持 $O(n \log n)$，空间复杂度为 $O(n)$。

若希望进一步夯实排序基础，可继续阅读仓库中的相关章节：