java - Java 基元数组上的 QuickSort 与 MergeSort

Question

我知道 Java 的 Arrays.sort 方法使用 MergeSort 对对象数组(或对象集合)进行排序，因为它是稳定的，而 Java 使用 QuickSort 对基元数组进行排序，因为我们不需要稳定性，因为两个相等的整数是不可区分的，即它们的身份无关紧要。

我的问题是，在原语的情况下，为什么 Java 不使用 MergeSort 的保证 O(n log n) 时间，而是使用 QuickSort 的平均 O(n log n) 时间？在一个相关答案的最后一段here ，解释说:

For reference types, where the referred objects usually take up far more memory than the array of references, this generally does not matter. But for primitive types, cloning the array outright doubles the memory usage.

这是什么意思？克隆一个引用仍然至少和克隆一个原语一样昂贵。在基元数组上使用 QuickSort(平均 O(n log n))而不是 MergeSort(保证 O(n log n) 时间)还有其他原因吗？

Answer 1

并非所有 O(n log n) 算法都具有相同的常数因子。快速排序在 99.9% 的情况下需要 n log n 时间，运行速度比合并排序快得多。我不知道确切的乘数——它会因系统而异——但是，比方说，快速排序的平均运行速度可能是合并排序的两倍，并且仍然具有理论上最坏情况下的 n^2 性能。

此外，快速排序不需要首先克隆数组，而归并排序则不可避免地需要。但是如果你想要一个稳定的排序，你就没有引用类型的选择，所以你必须接受副本，但你不需要接受原始类型的成本。