为什么Collections.sort使用合并排序而不是quicksort？

Question

我们知道快速排序是最快的排序算法。

JDK6 collections.sort使用合并排序算法而不是快速排序。但是Arrays.sort使用快速排序算法。

Collections.sort使用合并排序而不是快速排序的原因是什么？

Answer 1

极有可能从乔希布洛赫§：

我确实写了这些方法，所以我想我有资格回答。确实没有最佳的排序算法。与mergesort相比，QuickSort有两个主要缺陷：

1. 它不稳定（如parsifal所述）。

2. 它不能 保证 n log n的性能。在病理输入上，它可以降级为二次性能。

对于原始类型，稳定性是没有问题的，因为没有与（值）相等不同的身份概念。对于Bentely和McIlroy的实现（或随后的Dual Pivot
Quicksort
），实践中认为二次行为的可能性并不是问题，这就是为什么将这些QuickSort变体用于原始排序的原因。

排序任意对象时，稳定性至关重要。例如，假设您有代表电子邮件的对象，并且首先按日期对它们进行排序，然后再按发件人对它们进行排序。您希望它们在每个发件人中按日期进行排序，但是只有在排序稳定的情况下才是正确的。这就是为什么我们选择提供一个稳定的排序（合并排序）来对对象引用进行排序的原因。（从技术上讲，多个顺序稳定排序会导致键的字典顺序按排序的相反顺序进行：最终排序确定最高有效的子键。）

合并排序可以 保证 n log
n（时间）性能，无论输入什么，这都是一个很好的附带好处。当然有一个缺点：快速排序是“就地”排序：它仅需要登录n个外部空间（以维护调用堆栈）。另一方面，合并排序需要O（n）个外部空间。如果输入数组几乎已排序，则TimSort变体（在Java
SE 6中引入）需要的空间要少得多（O（k））。

另外，以下是相关的：

java.util.Arrays.sort和java.util.Collections.sort（间接）用于对对象引用进行排序的算法是一种“修改的mergesort”（如果低子列表中的最高元素小于，则忽略合并。高子列表中的最低元素）。”
这是一种相当快的稳定排序，可确保O（n log n）性能并需要O（n）额外空间。在当时（约书亚·布洛赫（Joshua
Bloch）于1997年撰写），这是一个不错的选择，但是今天，我们可以做得更好。

自2003年以来，Python的列表排序使用了一种称为timsort的算法（在Tim
Peters编写之后）。它是一种稳定的，自适应的，迭代的合并排序，在部分排序的数组上运行时，所需的比较少于n
log（n）个比较，而在随机数组上运行时，其性能可与传统的mergesort媲美。像所有适当的合并排序一样，timsort是稳定的，并且可以在O（n
log n）时间（最坏的情况）下运行。在最坏的情况下，timsort需要临时存储空间来存储n /
2个对象引用；在最佳情况下，它仅需要少量恒定的空间。与当前实现相反，当前实现始终需要额外的空间来存储n个对象引用，并且仅在几乎排序的列表上击败n log
n。

Timsort在此处进行了详细描述：http
://svn.python.org/projects/python/trunk/Objects/listsort.txt 。

蒂姆·彼得斯（Tim Peters）的原始实现是用C编写的。约书亚·布洛赫（Joshua
Bloch）将其从C移植到Java，并对其进行了最终测试，基准测试和广泛的调试。结果代码是java.util.Arrays.sort的直接替代。在高度排序的数据上，此代码的运行速度可高达当前实现（在HotSpot服务器VM上）的25倍。在随机数据上，旧的和新的实现的速度是可比的。对于非常短的列表，即使对随机数据，新的实现也比旧的实现快得多（因为它避免了不必要的数据复制）。

没有一个“最佳”选择。与许多其他事情一样，这是权衡的。