Timsort - 混合、稳定、高效的排序算法

2002 年，Tim Peters 开发了 Timsort 排序算法。它巧妙地结合了合并排序和插入排序的思想，并且设计得能很好地处理现实世界中的数据。TimSort 最初在 Python 开发的，但后来移植到了 Java (在 Java 中它以 java.util.Collections.sort 和 java.util.Arrays.sort 的形式出现) ，现在已经成为 Android SDK、 Sun 的 JDK 和 OpenJDK 的默认排序算法。

它是一种自适应、混合的、稳定 排序算法

Timsort 基于

• 插入排序(折半插入)

• 归并排序(分治思想， 分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)

Timsort 定义

• N : 数组长度。

• run：将数组通过一个算法划分成一个个子数组 （切割出来的 run 是严格升序或严格降序的）。

• minrun： 子数组最小的长度。

Timsort 原理

它的整体思路是这样的：

1. 遍历数组，将数组分为若干个升序或降序的片段，（如果是降序片段，反转降序的片段使其变为升序），每个片段称为一个 Run

2. 从数组中取一个 Run，将这个 Run 压栈。

3. 取出栈中相邻两个的 Run，做归并排序，并将结果重新压栈。

4. 重复(2),(3)过程，直到所有数据处理完毕。

时间复杂度和空间复杂度

Timsort 的平均排序时间与 MergeSort 相同，因此它比大多数的算法都要快。

Timsort 的作者 Tim Peters 认为在大多数情况下，我们给定的数组通常都是部分已经排好序的（严格单调递增或严格单调递减）。

Timsort 执行条件？

在 Python 中，如果待排序元素的个数少于 64 个，则 Timsort 将执行插入排序。而在 JDK 的版本中则是 32 个。

JDK1.8

步骤一：切割 Run

1. 根据 N 计算 MinRun 的长度

private static int minRunLength(int n) {    assert n >= 0;    int r = 0;      // Becomes 1 if any 1 bits are shifted off    while (n >= MIN_MERGE) {        r |= (n & 1);   //         n >>= 1;    }    return n + r;}

让我们来看看 minrun 是如何选择的，通过代码我们可以看出，

1) n & 1 判断 n 是否为偶数，返回 0 则是偶数，返回 1 则是奇数。

2) r = 0， 当偶数的情况下，0 = (n & 1) , 奇数时，1 = (n & 1)。 ｜运算保证只要其中一个的某一位 3）为 1，则结果的该位就为 1。

4) n >> 1 效果等同于 n / 2

n = 奇数，return (n-1) / 2 + 1。n = 偶数，return n / 2

假设 n 是 32，所以 minrun 的长度则是 16，而如果 n<32，则根本不会使用 Timsort。

通常，minrun 的取值不适合太长（影响插入排序效率），也不适合太小（归并排序的次数增多）， 在理想的情况，2 的幂次方或者接近 2 的幂次方在归并排序时的效率是最好的。（Timsort 作者通过实验认为 32 - 64 之间是最好的）

2. 从 Array[i] 扫描到 Array[N - 1] , 将原本严格单调递减的序列反转为单调递增的序列。

[1, 10, 9, 8, 2, 2, 5, 3, 6, 4, 7]

[1, 10, 2, 8, 9, 2, 3, 5, 4, 6, 7] 第六个 2 并没有翻转，因为它没有序列

此时，假设 minrun 的长度为 4

[1, 10] 还差两个元素，所以通过插入排序（折半）将后面的 2，8 插入进来，所以 run 1 就变成了

[1, 2, 8, 10]

run 2 还剩下一个 9， 长度也不满足 4， 所以，将后面 2，3，5 的插入进来，变成了

[2, 3, 5, 9]

还剩下一个 run 3

[4, 5, 7]

最终 run1、run2、run3 成了这个样子

[1, 2, 8, 10] [2, 3, 5, 9] [4, 5, 7]

不断重复步骤并将 run push 到栈中。

步骤二：合并

在这一步，我们将合并两个连续的 run。这个合并操作需要有一个临时数组来完成操作。

比方说 [1, 2, 2, 3, 5, 8, 9, 10] 和 [4, 5, 7, 11, 20, 35]这个例子。（run1 and run2）

1. 两个 run 中长度最小作为临时数组的长度，并将这个较小的 run 复制到临时数组里（后续操作中 run2 的数组会被覆盖）。

取 run1 的第一个元素 run1[base1]，剩余元素数量为 len1， 和 run2 的第一个元素下标 run2[base2]。

将 run2[base2]的元素 4 在 run1 数组中做二分查找，将 run1 数组中小于等于 run2[base2]的元素作为起始点，也就是 3。将 run1[base1 + len1 – 1]的元素 9，在 run2 中进行二分查找，大于等于 run1[base1 + len1 – 1]值的段作为结果的结束部分。

该例子中为元素 11 所在的下标。目的是为了[1, 2, 2, 3, 5, 8, 9, 10]， [4, 5, 7, 11, 20, 35]之间的元素。

1. 创建一个临时数组，将 run2 剩余的数组拷贝进去。

2. 将临时 run 和较大的 run 的标记段元素标记为起始位置。

3. 比较两个起始位置的元素的大小，将较小的一个移到目标数组，然后将起始位置移回。

4. 重复步骤 4，直到其中一个数组的元素全部取完。

5. 将未取完的 run 中剩余的所有元素添加到目标数组的末尾。

Timsort 的合并平衡性

为了保证 Timsort 的合并平衡性，Tim 制定一个合并规则，对于在栈顶的三个run，用X、Y和Z分别表示他们的长度，其中X在栈顶，必须始终维持一下的两个规则：

• Z >Y + X

• Y > X

一旦有其中的一个条件不被满足，Y这个子序列就会和X于Z中较小的元素合并形成一个新run，然后会再次检查栈顶的三个run看看是否仍然满足条件。如果不满足则会继续进行合并，直至栈顶的三个元素（如果只有两个run就只需要满足第二个条件）满足这两个条件。

感兴趣可以进一步了解

galloping mode

如果本文有错误的地方，欢迎指出！

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

https://awdesh.medium.com/timsort-fastest-sorting-algorithm-for-real-world-problems-1d194f36170e

https://cloud.tencent.com/developer/article/1518016