为什么Collections.sort使用合并sorting而不是快速sorting？
我们知道快速sorting是最好的sortingalgorithm。
collections.sort使用合并sortingalgorithm而不是快速sorting。 但是Arrays.sort使用快速sorting。
Collections.sort使用合并sorting而不是快速sorting的原因是什么？
很可能来自Josh Bloch§：
我写了这些方法，所以我想我有资格回答。 确实没有单一的最佳sortingalgorithm。 与mergesort相比，QuickSort有两个主要缺陷：
这是不稳定的（如parsifal指出）。
它不保证 n日志性能; 它可以退化到病理input的二次performance。
对于原始types来说，稳定性不是问题，因为没有认同（value）相等的概念。 在Bentely和McIlroy的实现（或随后的Dual Pivot Quicksort ）实践中，二次行为的可能性被认为不是问题，这就是为什么这些QuickSort变体被用于原始types的原因。
sorting任意对象时，稳定性是一件大事。 例如，假设您有表示电子邮件的对象，并按发送datesorting。 您希望他们在每个发件人中按datesorting，但只有sorting稳定时才会这样。 这就是为什么我们select提供稳定的sorting（合并sorting）来sorting对象引用。 （从技术上讲，多个顺序稳定的sorting会导致按照与sorting相反顺序sorting的按键sorting：最终的sorting决定了最重要的子键。
无论input什么，合并sorting都能保证 n日志（时间）性能，这是一个很好的优势。 当然有一个缺点：快速sorting是一个“就地”sorting：它只需要login外部空间（维护调用堆栈）。 另一方面，合并，sorting需要O（n）外部空间。 如果input数组几乎被sorting，则TimSort变体（在Java SE 6中引入）需要相当less的空间（O（k））。
另外， 以下是相关的：
java.util.Arrays.sort和java.util.Collections.sort（间接）用来对对象引用进行sorting的algorithm是一个“修改后的mergesort（如果低于sublist中最高的元素小于高级子列表中最低的元素）“。 这是一个合理的快速稳定sorting，保证O（n log n）的性能，并且需要O（n）额外的空间。 在它的那一天（它是由Joshua Bloch在1997年写的），这是一个很好的select，但今天，但我们可以做得更好。
自2003年以来，Python的列表sorting已经使用了一种称为timsort的algorithm（在Tim Peters编写之后）。 它是一个稳定的，自适应的，迭代式的mergesort，当在部分sorting的数组上运行时，需要远less于n个log（n）的比较，同时在随机数组上运行时性能堪比传统的mergesort。 像所有合适的合并sorting一样，timsort是稳定的，并且运行在O（n log n）时间（最坏的情况）。 在最坏的情况下，timsort需要临时存储空间来存放n / 2个对象; 在最好的情况下，它只需要很小的空间。 将其与当前的实现相比较，它总是需要额外的空间用于n个对象引用，并且仅在几乎sorting的列表上才能胜出。
Timsort在这里详细描述： http ://svn.python.org/projects/python/trunk/Objects/listsort.txt。
Tim Peters最初的实现是用C语言编写的。Joshua Bloch将它从C移植到Java，最后进行testing，基准testing和广泛调优。 生成的代码是java.util.Arrays.sort的一个embedded式替代品。 在高度有序的数据上，这个代码最多可以运行25倍（在HotSpot服务器虚拟机上）。 在随机数据上，旧的和新的实现的速度是可比的。 对于非常短的列表，即使是随机数据（因为它避免了不必要的数据复制），新的实现速度要快得多。
另请参阅使用Tim Sort作为Method Arrays.Sort的Java 7。 。
没有一个“最好”的select。 与其他许多事情一样，这是关于权衡的。
