闲逛的Timsort

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合并运行。