Grokking Timsort [英] Grokking Timsort

问题描述

有一个名为Timsort块上（相对）新的排序。它被用来作为Python的list.sort，现在将是<一href="http://download.java.net/jdk7/docs/api/java/util/Arrays.html#sort%28java.lang.Object%5B%5D">the新的Array.sort在Java 7中）。

There's a (relatively) new sort on the block called Timsort. It's been used as Python's list.sort, and is now going to be the new Array.sort in Java 7).

有一些文档和的微小的维基百科文章描述的排序和一些低层次的绩效评估的高层次性，但我很好奇，如果任何人都可以提供一些伪code说明什么Timsort是干什么的，究竟什么是使活泼的关键的东西。 （特别是相对于所引用的论文乐观排序与信息理论复杂性。）

There's some documentation and a tiny Wikipedia article describing the high-level properties of the sort and some low-level performance evaluations, but I was curious if anybody can provide some pseudocode to illustrate what Timsort is doing, exactly, and what are the key things that make it zippy. (Esp. with regard to the cited paper, "Optimistic Sorting and Information Theoretic Complexity.")

（参见<一个href="http://stackoverflow.com/questions/154504/is-timsort-general-purpose-or-python-specific">related StackOverflow的帖子。）

推荐答案

您应该看看这个博客帖子：的形象化排序算法：Python的timsort

You should look at this blog post: Visualising Sorting Algorithms: Python's timsort

摘要

timsort的企业到底是一个合并，经营上的pre排序元素运行。最小游程长度minrun被选择，以确保最终的合并是尽可能平衡 - 对64个元素，minrun恰好是32之前合并开始，单程通过数据以检测$ P $对现有分类元素的运行。降序运行由简单地扭转他们在的地方来处理。如果所得到的游程长度小于minrun，它被升压用插入排序到minrun。在一个洗牌阵列没有显著pre-现有的运行，这个过程看起来很像我们的猜测之上：pre-排序minrun元素块中的插入排序，合并与合并排序之前

The business-end of timsort is a mergesort that operates on runs of pre-sorted elements. A minimum run length minrun is chosen to make sure the final merges are as balanced as possible - for 64 elements, minrun happens to be 32. Before the merges begin, a single pass is made through the data to detect pre-existing runs of sorted elements. Descending runs are handled by simply reversing them in place. If the resultant run length is less than minrun, it is boosted to minrun using insertion sort. On a shuffled array with no significant pre-existing runs, this process looks exactly like our guess above: pre-sorting blocks of minrun elements using insertion sort, before merging with merge sort.

[...]

• timsort发现了一个下降的运行，并逆转就地运行。这是指针数组上直接完成，所以显得即时从我们的有利位置。
• 的运行现在使用插入排序提升至长minrun。
• 否运行处检测下一个块的开始，和插入排序，用于整个块进行排序。需要注意的是，在该块的底部的排序元素没有特殊处理。 - timsort没有检测运行启动中的块的中间被升压到minrun
• 最后，归并用于合并运行。

这篇关于Grokking Timsort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！