java - 闲逛的Timsort

块上有一个(相对)新的名为Timsort的排序。它已被用作Python的list.sort，现在将是the new Array.sort in Java 7。

有some documentation和tiny Wikipedia article描述了排序的高级属性以及一些低级的性能评估，但我很好奇是否有人可以提供一些伪代码来说明Timsort的功能，确切的功能以及使它起作用的关键因素zippy。 (特别是对于引用的论文“乐观排序和信息理论复杂性”。)

(另请参见related StackOverflow post。)

最佳答案

引用现在已删除的博客文章的相关部分:Visualising Sorting Algorithms: Python's timsort



[...]

timsort查找降序运行，并就地反转运行。这是直接在指针数组上完成的，因此从我们的角度来看似乎“即时”。

现在，使用插入排序将运行提高到minrun长度。

在下一个块的开始处未检测到运行，并且插入排序用于对整个块进行排序。请注意，该块底部的排序元素未得到特别处理-timsort不会检测到从被提升为minrun的块中间开始的运行。

最后，使用mergesort合并运行。