我在面试时被问到这个问题。它们都是 O(nlogn)，但大多数人使用快速排序而不是合并排序。这是为什么？

请您参考如下方法:

快速排序的最坏情况运行时间为 O(n²)，平均情况运行时间为 O(nlogn)。但是，在许多情况下它都优于合并排序，因为许多因素都会影响算法的运行时间，并且当将所有因素综合考虑时，快速排序会胜出。

特别是，经常引用的排序算法的运行时间是指对数据进行排序所需的比较次数或交换次数。这确实是一个很好的性能衡量标准，特别是因为它独立于底层硬件设计。然而，其他因素——例如引用的局部性(即我们是否读取了可能在缓存中的大量元素？)——在当前的硬件上也发挥着重要作用。特别是快速排序只需要很少的额外空间并表现出良好的缓存局部性，这使得它在许多情况下比合并排序更快。

此外，通过使用适当的主元选择，例如随机选择它(这是一个很好的策略)，几乎可以完全避免快速排序最坏情况下的 O(n²) 运行时间。

实际上，快速排序的许多现代实现(特别是 libstdc++ 的 std::sort)实际上是 introsort ，理论上最坏情况是 O(nlogn)，与归并排序相同。它通过限制递归深度并在超过 logn 时切换到不同的算法 ( heapsort ) 来实现这一点。