Java & 归并排序

Question

为什么 Java impl 选择合并排序而不是快速排序？为什么他们将内容复制到数组中？

API:“排序算法是修改后的合并排序(如果低子列表中的最高元素小于高子列表中的最低元素，则合并被忽略)。该算法提供有保证的 n log(n) 性能. 此实现将指定的列表转储到数组中，对数组进行排序，并遍历列表，从数组中的相应位置重置每个元素。这避免了尝试对链表进行排序时导致的 n2 log(n) 性能到位。”

Answer 1

Java 人员将最坏情况与平均情况进行了交易，您可能知道，在最坏情况下，快速排序可能在 O(n^2) 中运行。

您可以在 API 中阅读，就地排序链表更复杂 n^2log(n)

归并排序是稳定的，而高效版本的快速排序则不然。(这在排序对象时非常重要 + 许多程序员在使用 Collections.sort() 时认为这是理所当然的)