java - java中的合并排序和复制数组，仍然是nlogn？

Question

我已经研究了java中合并排序的一些实现，似乎分割部分通常是通过创建两个新数组(左数组和右数组)并将左数组和右数组分别复制到这些数组来完成的。

我的问题是:这仍然给我们 nlogn 时间，对吗？因为现在每次分割都会有 n+n 次(n 次分割数组，n 次合并数组)，并且有 logn 次分割，所以我们有 2nlogn ，仍然是 nlogn 。这是正确的吗？

Answer 1

您正在考虑哪些实现？ JDK使用的主要排序算法是DualPivotQuicksort (对于原始数组)，TimSort和 ComparableTimSort (对于 Object 数组/集合)，以及 ArraysParallelSortHelpers 中难以理解的魔法用于并发排序。

所有这些类都提供了 QuickSort 或 MergeSort 的高度调整的实现(或者在并行情况下 "CilkSort" ，这听起来像是并发友好的 MergeSort)。这些算法通常都是 O(n log(n)) - 它是 impossible to do better than O(n log(n))对您的输入没有额外的限制。

至于这些算法是否通常花费 O(n) 时间在临时存储之间来回复制值，这很大程度上是一个具体问题具体分析的问题。在可能的情况下，这些实现肯定会尝试避免使用 O(n) 额外内存和时间来进行线性复制，但通常此类工作实际上并不是瓶颈。例如，CilkSort 使用辅助“工作空间数组”在连续阶段中来回复制值，这使得更容易强制执行不变量，因为“先前”阶段始终处于可靠状态。即使如此，实现也会尽可能避免不必要的数组副本。

在公共(public) API 级别，我们会注意到 Collections.sort() 调用 .toArray()，对数组进行排序，然后将值复制回原始列表。这同样只是一个实用的优化 - 对数组进行排序并执行两个线性副本比处理所有方法调用(以及可能效率低下的 List 实现，例如 LinkedList)更快>) 就地修改List。