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

EN

很可能来自Josh Bloch §

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

1. 它不稳定(正如parsifal所指出的)。
2. 它不能保证not性能；它可以在病态输入上降级为二次性能。

对于原语类型来说，稳定性是不成问题的，因为没有区别于(值)相等的同一性概念。对于Bentely和McIlroy的实现(或随后的Dual Pivot Quicksort)，二次行为的可能性被认为在实践中不是问题，这就是为什么这些QuickSort变体用于原始排序。

在对任意对象进行排序时，稳定性是一个很重要的问题。例如，假设您有表示电子邮件消息的对象，并且首先按日期排序，然后按发件人排序。您希望它们在每个发送者中按日期排序，但只有在排序稳定的情况下才会这样。这就是为什么我们选择提供一个稳定的排序(合并排序)来对对象引用进行排序。(从技术上讲，多个顺序稳定的排序导致键上的字典顺序与排序的顺序相反:最终的排序确定最重要的子键。)

无论输入是什么，合并排序都能保证n log n(时间)性能，这是一个很好的附带好处。当然也有缺点:快速排序是一种“就地”排序:它只需要log n个外部空间(用来维护调用堆栈)。另一方面，合并、排序需要O(n)个外部空间。如果输入数组几乎是有序的，则TimSort变体(在JavaSE6中引入)所需的空间(O(k))要小得多。

此外，following也是相关的：

java.util.Arrays.sort和(间接) java.util.Collections.sort用来对对象引用进行排序的算法是“修改的合并排序(其中，如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并)”。它是一种相当快速、稳定的排序，保证了O(n log n)的性能，并且需要O(n)额外的空间。在它的时代(它是由Joshua Bloch在1997年写的)，这是一个很好的选择，但今天我们可以做得更好。

从2003年开始，Python的列表排序就使用了一种称为timsort的算法(以Tim Peters的名字命名)。它是一个稳定的，自适应的，迭代的合并排序，当在部分排序的数组上运行时，需要远少于n log(n)的比较，而当在随机数组上运行时，它提供了与传统合并排序相当的性能。像所有合适的合并排序一样，timsort是稳定的，运行时间是O(n log n) (最坏的情况)。在最坏的情况下，timsort需要用于n/2个对象引用的临时存储空间；在最好的情况下，它只需要少量恒定的空间。这与当前的实现形成了对比，当前的实现总是需要额外的空间来引用n个对象，并且只有在几乎排序的列表上才能击败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倍。在随机数据上，新旧实现的速度是相当的。对于非常短的列表，即使是在随机数据上，新实现也比旧实现快得多(因为它避免了不必要的数据复制)。

另请参见Is Java 7 using Tim Sort for the Method Arrays.Sort?。

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