java - 摸索蒂姆索特

Question

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

有一些文档和一篇很小的 Wikipedia 文章描述了排序的高级属性和一些低级性能评估，但我很好奇是否有人可以提供一些伪代码来说明 Timsort 到底在做什么，以及关键的事情是什么这使它变得活泼。（特别是关于被引用的论文，“乐观排序和信息论复杂性”。）

（另请参阅相关的 StackOverflow 帖子。）

Answer 1

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

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

[...]

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

Answer 2

此更改在进入时通过了core-libs 邮件列表，因此那里有一些讨论和有用的链接。这是带有代码审查更改的网络版本以及原始补丁。

代码中的注释说：

实现说明：此实现是一种稳定的、自适应的、迭代的归并 排序，当输入数组部分排序时，
它需要远少于 n 次 lg(n) 比较，而当输入数组是 随机排序时，它提供 传统归并排序的性能。如果输入数组接近排序，则 实现需要大约 n 次比较。 临时存储要求从几乎排序的 输入数组的小常数到随机排序的输入数组的 n/2 对象引用不等 。

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

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