何时使用合并排序，何时使用快速排序？

Question

wikipedia article for merge sort。

wikipedia article for quick sort。

这两篇文章都有出色的可视化效果。

两者都具有n*log(n)复杂度。

所以很明显，数据的分布会影响排序的速度。我的猜测是，由于比较可以快速地比较任何两个值，无论它们的分布如何，数据值的范围都无关紧要。

更重要的是，应该考虑相对于排序(去除幅度)的横向分布(x方向)。

一个不错的测试用例是如果测试数据具有某种级别的排序...

Answer 1

Java6和更早的版本使用合并排序作为排序算法，而C#使用QuickSort作为排序算法。

QuickSort比合并排序性能更好，即使它们都是O(nlogn)。快速排序的常量比合并排序的常量小。

Answer 2

它通常取决于所涉及的数据结构。快速排序通常是最快的，但它不能保证O(n*log(n))；在一些退化的情况下，它变成O(n^2)。堆排序是通常的替代方案；无论初始顺序如何，它都保证O(n*log(n))，但它具有更高的常量因子。它通常在你需要一个时间的硬性上限时使用。一些较新的算法使用快速排序，但尝试识别它何时开始退化，然后切换到堆排序。合并排序在数据结构不支持随机访问时使用，因为它适用于纯顺序访问(前向迭代器，而不是随机访问迭代器)。例如，它在std::list<>::sort中使用。它还广泛用于外部排序，与顺序访问相比，随机访问可能非常非常昂贵。(在对不适合内存的文件进行排序时，您可以将其拆分成适合内存的块，使用快速排序对这些块进行排序，将每个文件写出到一个文件中，然后对生成的文件进行合并排序。)

Answer 3

Mergesort在处理链表时速度更快。这是因为在合并列表时指针可以很容易地改变。它只需要一次遍历列表(O(n))。

快速排序的就地算法需要数据的移动(交换)。虽然这对于内存中的数据集是非常有效的，但如果您的数据集不适合内存，那么它的成本可能会高得多。结果将是大量的I/O。

如今，出现了大量的并行化。并行化Mergesort比Quicksort (就地)简单。如果不使用就地算法，则快速排序的空间复杂度为O(n)，这与合并排序相同。

因此，一般而言，快速排序对于适合内存的数据集可能更有效。对于较大的内容，最好使用mergesort。

使用合并排序而不是快速排序的另一个一般情况是，如果数据非常相似(也就是说，不是接近一致)。快速排序依赖于使用轴心。在所有值都相似的情况下，快速排序的最坏情况是O(n^2)。如果数据的值非常相似，那么很可能会选择一个糟糕的透视，从而导致非常不平衡的分区，从而导致O(n^2)运行时间。最直接的例子是列表中的所有值都是相同的。