timsort与quicksort的比较

Question

为什么我经常听说快速排序是最快的整体排序算法，而Timsort (根据wikipedia)似乎表现得更好？谷歌似乎没有发现任何形式的比较。

Answer 1

TimSort是一种高度优化的合并排序，它比传统的合并排序更稳定、更快。

与快速排序相比，它有两个优点：

1. 对于几乎排序的数据序列(包括反向排序的数据)来说，它的速度令人难以置信；
2. 最坏的情况仍然是O(N*LOG(N))。

老实说，我不认为#1是一个优势，但它确实给我留下了深刻的印象。

以下是快速排序的优点

1. QuickSort非常简单，即使是一个高度调优的实现，我们也可以在20 lines;
2. QuickSort内写下它的pseduo代码在大多数情况下是最快的；
3. 内存消耗是LOG(N)。

目前，Java7SDK实现了timsort和一个新的快速排序变体:即Dual Pivot QuickSort。

如果你需要稳定的排序，尝试timsort，否则从快速排序开始。

Answer 2

一般来说，快速排序是基元数组的最佳算法。这是由于内存局部性和高速缓存造成的。

JDK7使用TimSort作为Object数组。对象数组只保存对象引用。对象本身存储在Heap中。为了比较对象，我们需要从堆中读取对象。这就像从堆的一部分读取一个对象，然后从堆的另一部分随机读取对象。将会有很多缓存未命中。我猜由于这个原因，内存的局部性不再重要了。这可能就是为什么JDK只将TimSort用于对象数组而不是原始数组的原因。

这只是我的猜测。

Answer 3

以下是我机器上的基准测试数据(i7-6700CPU，3.4 gcc，Ubuntu16.04，gcc 5.4.0，参数: SIZE=100000和RUNS=3)：

$ ./demo 
Running tests
stdlib qsort time:                 12246.33 us per iteration
##quick sort time:                  5822.00 us per iteration
merge sort time:                    8244.33 us per iteration
...    
##tim sort time:                    7695.33 us per iteration
in-place merge sort time:           6788.00 us per iteration    
sqrt sort time:                     7289.33 us per iteration    
...
grail sort dyn buffer sort time:    7856.67 us per iteration

基准测试来自Swenson的sort项目，在该项目中，他用C语言实现了几个排序算法。大概，他的实现足够好，足以具有代表性，但我还没有研究过它们。

所以你真的看不出来。基准数字最多只会保持两年的相关性，然后你必须重复它们。也许，timsort在2011年被问到这个问题时就击败了qsort，但时代已经不同了。或者，qsort总是最快的，但timsort在非随机数据上胜过它。或者Swenson的代码不是很好，一个更好的程序员会扭转趋势，有利于timsort。或者我很糟糕，在编译代码时没有使用正确的CFLAGS。或者..。你说对了。