Grokking Timsort

algorithm sorting python java timsort

2022-09-01 19:20:48

在块上有一个（相对）新的排序，叫做Timsort。它已被用作Python的list.sort，现在将成为Java 7中新的Array.sort。

有一些文档和一篇小小的维基百科文章描述了这种类型的高级属性和一些低级性能评估，但我很好奇是否有人可以提供一些伪代码来说明Timsort到底在做什么，以及使它变得紧张的关键因素是什么。（特别是关于引用的论文，“乐观排序和信息理论复杂性”。

答案 1

引用现已删除的博客文章中的相关部分：可视化排序算法：Python的timsort

timsort 的业务端是对预排序元素的运行进行操作的合并排序。选择最小运行长度 minrun 以确保最终合并尽可能平衡 - 对于 64 个元素，minrun 恰好是 32。在合并开始之前，对数据进行一次传递，以检测已排序元素的预先存在的运行。下降运行只需将它们反转到位即可处理。如果生成的运行长度小于 minrun，则使用插入排序将其提升为 minrun。在没有显著的预先存在运行的随机数组上，此过程看起来与我们上面的猜测完全相同：在与合并排序合并之前，使用插入排序对minrun元素块进行预排序。

[...]

timsort 找到一个下降的运行，并反转原位运行。这是直接在指针数组上完成的，因此从我们的有利位置来看似乎是“即时的”。
现在，使用插入排序将运行提升为长度最小运行。
在下一个块的开头未检测到运行，插入排序用于对整个块进行排序。请注意，此块底部的排序元素不会得到特殊处理 - timsort 不会检测到在块的中间开始的运行，这些块被提升到 minrun。
最后，合并排序用于合并运行。

答案 2

这个变化在进入时通过core-libs邮件列表，所以那里有一些讨论和有用的链接。这是包含代码审查更改的Web修订版，也是原始补丁。

代码中的注释说：

实现说明：此实现是一种稳定的自适应迭代合并排序，

当输入数组部分排序时，它需要的比较次数远远少于 n 个 lg（n），同时在
输入数组随机
排序时提供传统合并排序的性能。如果输入数组几乎已排序，则
实现需要大约 n 个比较。
临时存储要求各不相同，从几乎排序的
输入数组的小常量到随机排序输入
数组的 n/2 对象引用。

该实现在其输入数组中同时利用升序和
降序，并且可以在同
一
输入数组的不同部分中利用升序和降序。它非常适合合并两个或多个排序的数组：
只需连接数组并对生成的数组进行排序即可。
该实现改编自Tim Peters对Python
TimSort的列表排序。它使用了Peter McIlroy的“乐观
排序和信息理论复杂性”中的技术，在第
四届年度ACM-SIAM离散算法研讨会论文集，第467-474页，
1993年1月。

埋藏在那里的是指向Python实现细节的非常有用的链接，我认为这是一个很好的起点，其次是代码。为了达到令人难以置信的高水平，timsort通过注意排序数据的运行并在排序期间利用该结构来提高性能。