这是一个相当老的问题，但因为我最近处理了这两个问题，所以这里是我的2c:

归并排序平均需要~ N log N次比较。对于已经(几乎)排序过的排序数组，这可以达到1/ 2nlog N，因为在归并时，我们(几乎)总是选择“左边”的1/ 2n次，然后只复制右边1/ 2n个元素。此外，我可以推测，已经排序的输入使处理器的分支预测器发光，但猜测几乎所有的分支都正确，从而防止管道停顿。

快速排序平均需要~ 1.38 nlog N个比较。在比较方面，它不会从已经排序的数组中获得很大的好处(但是在交换方面，可能在CPU内部的分支预测方面，它会获得很大的好处)。

我在相当现代的处理器上的基准测试显示如下:

当比较函数是回调函数时(如qsort() libc实现)，对于随机输入，快速排序比归并排序慢15%，对于已经排序的64位整数，快排序比归并排序慢30%。

另一方面，如果比较不是回调，我的经验是快速排序优于归并排序高达25%。

然而，如果你的(大)数组只有很少的唯一值，归并排序在任何情况下都开始超过快速排序。

因此，底线可能是:如果比较是昂贵的(例如，回调函数，比较字符串，比较结构的许多部分，主要是得到第二个，第三个，第四个“if”来产生差异)-很可能你会更好地使用归并排序。对于简单的任务，快速排序会更快。

之前所说的都是真的: -快速排序可以是N^2，但Sedgewick声称，一个好的随机实现有更多的机会，计算机执行排序被闪电击中比N^2 —归并排序需要占用额外空间

虽然它们都在相同的复杂度类中，但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快，因为它更容易编写紧凑的实现代码，它所做的操作也更快。这是因为快速排序通常更快，人们使用它而不是归并排序。

然而!我个人经常会使用归并排序或快速排序变体，当快速排序表现不佳时，它们会降级为归并排序。记住。快速排序平均只有O(n log n)最坏情况是O(n²)归并排序总是O(n log n).在实时性能或响应性是必须的情况下，你的输入数据可能来自恶意来源，你不应该使用简单的快速排序。

维基百科的解释是:

通常，快速排序在实践中比其他Θ(nlogn)算法要快得多，因为它的内部循环可以在大多数架构上有效地实现，并且在大多数现实数据中，可以做出设计选择，使需要二次时间的概率最小化。

快速排序

Mergesort

我认为归并排序(即Ω(n))所需要的存储量也存在快速排序实现所不具备的问题。在最坏的情况下，它们的算法时间是相同的，但归并排序需要更多的存储空间。

快速排序有O(n2)最差情况运行时和O(nlogn)平均情况运行时。然而，在许多情况下，它优于归并排序，因为许多因素影响算法的运行时，并且，当把它们放在一起时，快速排序胜出。

In particular, the often-quoted runtime of sorting algorithms refers to the number of comparisons or the number of swaps necessary to perform to sort the data. This is indeed a good measure of performance, especially since it’s independent of the underlying hardware design. However, other things – such as locality of reference (i.e. do we read lots of elements which are probably in cache?) – also play an important role on current hardware. Quicksort in particular requires little additional space and exhibits good cache locality, and this makes it faster than merge sort in many cases.

此外，通过使用适当的枢轴选择，几乎完全避免快速排序的最坏情况运行时间O(n2)是非常容易的——比如随机选择它(这是一个很好的策略)。

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

答案将略微倾向于快速排序w.r.t的变化带来的DualPivotQuickSort的基本值。它在JAVA 7中用于在JAVA .util. arrays中排序

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

您可以在这里找到JAVA7实现- http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

关于DualPivotQuickSort的进一步精彩阅读- http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

维基百科上关于快速排序的词条:

Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case Θ(nlogn) running time. Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage. Although quicksort can be written to operate on linked lists, it will often suffer from poor pivot choices without random access. The main disadvantage of mergesort is that, when operating on arrays, it requires Θ(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only Θ(logn) space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.)