tim排序

Author

tim 排序是归并排序和插入排序的结合，是一个 稳定 的排序算法，由 Tim Peters 于 2002 年用 Python 实现。现在，tim 排序是 Python 的标准排序算法，且被 Java SE7 用于对非原始类型的数组排序。

tim 排序在最好情况下的时间复杂度为 ，最差情况下的时间复杂度为 ，期望时间复杂度为 。tim 排序在最坏情况下的空间复杂度为 。

算法

众所周知，归并排序是先将数组划分为两部分，然后递归地对两个子数组进行归并排序，最后合并两个子数组。这样一来，归并排序合并操作的最小单位就是单个元素。但是，数组中可能原本就存在连续且有序的子数组，归并排序无法利用这个特性。

tim 排序为了利用数组中本身就存在的连续且有序的子数组，以 RUN 作为合并操作的最小单位。其中，RUN 是一个满足以下性质的子数组：

• 一个 RUN 要么是非降序的，要么是严格升序的。
• 一个 RUN 存在一个长度的下限。

tim 排序的过程就是一个类似归并排序的过程，将数组划分为多个 RUN，然后以某种规则不断地合并两个 RUN，直到数组有序。具体过程如下：

令 初始化为数组的大小， 初始化为 。

其中， 函数是根据当前数组长度确定 具体值的函数，natural run 的意思是原本就非降序或者严格升序的 run，扩展长度不够的 run 就是用插入排序往 run 中添加元素。

复杂度证明

最好情况下，数组本身就有序，即数组本身就是一个 RUN，这个时候 tim 排序就遍历了一遍数组，找到了唯一的 RUN，就结束了。所以，最好的情况下，tim 排序的时间复杂度为 。

写在后面

本文只是简单介绍了 tim 排序的原理，实际上 tim 排序在实现的时候还有一些其他的优化，这里不再一一列举。tim 排序在 java 中的实现写得非常好，要想知道真正的 tim 排序推荐去看 java 中 tim 排序的实现。

参考资料

1. Timsort
2. On the Worst-Case Complexity of TimSort
3. original explanation by Tim Peters
4. java 实现
5. c 语言实现