Grokking Timsort

Question

这块名为Timsort的(相对)新排序.它被用作Python的list.sort,现在将成为Java 7中的新Array.sort.

有一些文档和一篇小维基百科文章描述了排序的高级属性和一些低级别的性能评估,但我很好奇是否有人可以提供一些伪代码来说明Timsort正在做什么,确切地说,关键是什么这让它变得有趣.(参见引用的论文"乐观排序和信息理论复杂性".)

(另请参阅StackOverflow相关帖子.)

Answer 1

从现在删除的博客文章中引用相关部分:可视化排序算法:Python的时间顺序

timsort的业务端是一个mergesort,它运行预先排序的元素.选择最小游程长度minrun以确保最终合并尽可能平衡 - 对于64个元素,minrun恰好是32.在合并开始之前,通过数据进行单次传递以检测预先存在的已排序运行元素.通过简单地将它们反转就可以处理降序运行.如果得到的运行长度小于minrun,则使用插入排序将其提升到minrun.在没有显着预先存在的运行的混洗数组上,此过程看起来与我们上面的猜测完全相同:在使用合并排序合并之前,使用插入排序预先排序minrun元素块.

[...]

• timsort找到一个降序运行,并在原地反转运行.这是直接在指针数组上完成的,因此从我们的观点来看似乎是"即时的".
• 现在使用插入排序将运行提升到minrun长度.
• 在下一个块的开头没有检测到运行,并且插入排序用于对整个块进行排序.请注意,此块底部的已排序元素未经过特殊处理 - timsort不会检测在块被提升为minrun的过程中开始的运行.
• 最后,mergesort用于合并运行.

Answer 2

这个更改在进入时通过了core-libs邮件列表,因此在那里有一些讨论和有用的链接.这是带有代码审查更改的Web rev以及原始补丁.

代码中的评论说:

实现注意事项:此实现是一个稳定的,自适应的
迭代合并输出,
当输入数组被部分排序时,它需要远低于n lg(n)的比较,同时
在输入数组
随机排序时提供传统mergesort 的性能.如果输入数组几乎已排序,则
实现需要大约n次比较.
临时存储要求从几乎排序的
输入数组的小常量到随机排序的输入数组的n/2个对象引用不等
.

该实现
在其输入数组中具有
升序和降序的相同优点,并且可以利用相同
输入数组的不同部分中的升序和降序.它非常适合合并两个或多个排序数组:
只需连接数组并对结果数组进行排序.
该实现改编自Tim Peters的Python
TimSort列表排序.它使用了Peter McIlroy的"乐观
排序和信息理论复杂性"中的技术,参见"
第四届年度ACM-SIAM离散算法研讨会论文集",第467-474页,
1993年1月.

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