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

很可能来自Josh Bloch §：

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

1. 它不稳定（正如parsifal所指出的）。

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

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

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

合并排序保证了 n log n（时间）性能，无论输入什么，这都是一个不错的附带好处。当然，也有一个缺点：快速排序是一种“就地”排序：它只需要log 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） 比较，同时在随机数组上运行时提供与传统合并排序相当的性能。像所有正确的合并排序一样，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 的直接替换。在高排序数据上，此代码的运行速度最高可达当前实现的 25 倍（在 HotSpot 服务器 VM 上）。在随机数据上，新旧实现的速度相当。对于非常短的列表，即使在随机数据上，新实现也比旧实现快得多（因为它避免了不必要的数据复制）。

另请参阅 Java 7 是否对方法数组使用 Tim Sort。Sort？。

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