javascript - 什么是 Array.prototype.sort() 时间复杂度？

Question

根据 Mozilla 文档：

排序的时间和空间复杂度不能保证，因为它取决于实现。

至少可以安全地假设它不是O(n^2)吗？有没有关于它是如何实施的更详细的数据？谢谢。

标签： javascript

Answer 1

Firefox 使用归并排序。从 70 版开始，Chrome 使用合并排序和插入排序的混合体，称为Timsort。

归并排序的时间复杂度为O(n log n)。虽然规范没有指定要使用的排序算法，但在任何严重的环境中，您可能会期望对较大的数组进行排序不会花费更长的时间O(n log n)（因为如果这样做了，那么很容易更改为更快的算法，例如合并排序，或其他一些对数线性方法）。

虽然像归并排序这样的比较排序的下限为O(n log n)（即它们至少需要这么长时间才能完成），但 Timsort 利用已排序数据的“运行”优势，因此下限为O(n).