Timsort排序算法详解

Timsort排序算法详解

Timsort是一种混合的、稳定的排序算法，由Python核心开发者Tim Peters于2002年设计。它巧妙地结合了插入排序和归并排序的优点，特别适合处理包含大量部分有序子序列的数据集。自Python 2.3版本以来，Timsort被选为Python标准库的默认排序算法，并被广泛应用于其他编程环境。

引入

Timsort由Python核心开发者Tim Peters于2002年设计，并应用于Python语言，其巧妙结合了插入排序和归并排序的优点，针对数据集中的有序性进行了精确的优化，尤其适合处理包含大量部分有序子序列的数据集。自Python 2.3版本以来，Timsort被选为Python标准库的默认排序算法，并被广泛应用于其他编程环境，例如在Java SE 7中被用于对非原始对象数组进行排序。

步骤

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

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

识别Run

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

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

扩展Run

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

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

归并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时提高效率并减少空间开销，Timsort在归并前会通过二分查找精确定位需要处理的元素范围，只对需要移动的部分进行归并，具体方式为：

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

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

• Run A:
• Run B:

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

• 元素应插入到Run A的第四个位置。
• 元素应插入到Run B的第五个位置。

因此，Run A的前个元素和Run B的后个元素已经在正确位置，无需处理。只需归并Run A的和Run B的，其归并过程如下图所示：

加速模式

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

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

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

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

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

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

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

复杂度

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

• 最优情况：

• 当数据已经有序或近似有序时，算法识别出的Run长度接近，归并次数减少，复杂度趋近于。

• 最坏情况：

• 在数据完全无序的情况下，每一个Run的长度都接近，因此需要次归并，每次归并的代价为，总复杂度为。

证明：

• 识别和扩展Run：

• 识别Run需线性遍历一次数组，其复杂度为。

• 使用插入排序扩展Run也需线性遍历数组，其复杂度为。

• 归并Run：

• 归并操作的总次数与Run的总数有关，最坏情况下Run的数量为n / MIN_RUN，由于MIN_RUN是常数，因此Run的数量可看作。

• 个Run需要进行的归并次数为，每次归并操作的代价为，因此归并操作的总复杂度为。

而对于空间复杂度，由于Timsort大致需要额外的空间用于存储栈和临时缓冲区，因此总的空间复杂度为。

实现

伪代码实现

参考资料