理解Timsort
最近出现了一种新的排序算法，叫做Timsort。它被用在Python的list.sort中，现在也将成为Java 7中的新Array.sort。
有一些文档和一篇小维基百科文章，介绍了这种排序算法的基本特性和一些性能评估。不过我很好奇有没有人能提供一些伪代码，来具体说明Timsort是如何工作的，以及它的关键之处是什么，让它运行得这么快。（特别是关于那篇提到的论文，“乐观排序与信息理论复杂性”。）
（另见相关的StackOverflow帖子。）
2 个回答
这个变化在 core-libs 邮件列表 上讨论过，所以那里有一些讨论和有用的链接。这里有一个 网页版本，里面有代码审查的变化，还有一个 原始补丁。
代码中的注释提到：
实现说明：这个实现是一种稳定的、自适应的、迭代的归并排序，当输入数组部分有序时，它需要的比较次数远少于 n lg(n)，而当输入数组是随机顺序时，它的性能与传统的归并排序相当。如果输入数组几乎是有序的，实施大约需要 n 次比较。临时存储的需求从几乎有序的输入数组的一个小常量，到随机顺序输入数组的 n/2 个对象引用不等。
这个实现同样利用了输入数组的升序和降序，并且可以利用同一个输入数组中不同部分的升序和降序。它非常适合合并两个或多个已排序的数组：只需将这些数组连接起来，然后对结果数组进行排序。这个实现是从 Tim Peters 为 Python 设计的列表排序算法 TimSort 中改编而来的。它使用了 Peter McIlroy 的“乐观排序和信息理论复杂性”中的一些技术，相关论文发表于1993年1月的第四届ACM-SIAM离散算法年会。
在这里面有一个 非常有用的链接，提供了Python实现的细节，我觉得这是一个很好的起点，然后再看代码。简单来说，timsort通过识别已排序数据的连续段来提高性能，并在排序过程中利用这种结构。
引用一篇现在已经删除的博客文章中的相关部分：可视化排序算法：Python的timsort
timsort的核心其实是一个合并排序，它是针对已经排好序的元素块进行操作的。为了让最后的合并尽可能平衡，我们选择一个最小的块长度，叫做minrun。对于64个元素来说，minrun的值是32。在开始合并之前，先对数据进行一次遍历，找出已经排好序的元素块。如果发现有降序的块，就直接把它们反转过来。如果反转后的块长度小于minrun，就用插入排序把它的长度提升到minrun。在一个打乱的数组中，如果没有明显的已经排好序的块，这个过程就和我们之前的猜测完全一样：先用插入排序对minrun大小的元素块进行预排序，然后再用合并排序进行合并。
[...]
- timsort发现了一个降序的块，并直接在原地反转了这个块。这是直接在指针数组上进行的，所以从我们的角度看起来是“瞬间”完成的。
- 然后用插入排序把这个块的长度提升到minrun。
- 在下一个块的开始时没有发现任何块，整个块都用插入排序进行排序。需要注意的是，这个块底部已经排好序的元素并没有被特别处理——timsort不会检测到在提升到minrun的块中间开始的序列。
- 最后，使用合并排序来合并这些块。