快速排序具有更好的平均情况复杂度，但在某些应用中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入，他可以很容易地构造一个时间复杂度为o(n^2)的最坏情况的集合。

归并排序的平均情况复杂性和最坏情况复杂性是相同的，因此不会遇到相同的问题。归并排序的这一特性也使它成为实时系统的最佳选择——确切地说，因为没有导致它运行得非常非常慢的病理情况。

由于这些原因，我更喜欢归并排序，而不是快速排序。

在归并排序中，一般算法为:

对左子数组进行排序 对右子数组进行排序 合并两个已排序的子数组

在顶层，合并两个已排序的子数组涉及处理N个元素。

再往下一层，第3步的每次迭代都涉及处理N/2个元素，但您必须重复此过程两次。所以你仍然在处理2 * N/2 == N个元素。

再往下一层，你要合并4 * N/4 == N个元素，以此类推。递归堆栈中的每个深度都涉及合并相同数量的元素，涉及对该深度的所有调用。

考虑一下快速排序算法:

选择一个枢轴点 将枢轴点放置在数组中的正确位置，所有较小的元素放在左边，较大的元素放在右边 对左子数组进行排序 对右子数组排序

在顶层，你处理的是一个大小为n的数组，然后选择一个枢轴点，把它放在正确的位置，然后可以在算法的其余部分完全忽略它。

再往下一层，您将处理2个子数组，它们的组合大小为N-1(即减去之前的枢轴点)。为每个子数组选择一个枢轴点，总共有2个额外的枢轴点。

再往下一层，您将处理4个子数组，它们的组合大小为N-3，原因与上面相同。

然后N-7…然后c15…然后N-32…

递归堆栈的深度保持大致相同(logN)。使用归并排序，你总是在递归堆栈的每一层处理n个元素的归并。但是使用快速排序，你要处理的元素数量会随着你在堆栈中向下移动而减少。例如，如果你在递归堆栈中查看深度，你正在处理的元素数量是N - 2^((logN)/2)) == N -根号(N)。

声明:对于归并排序，因为每次都将数组分割为两个完全相等的块，所以递归深度正好是logN。在快速排序时，由于枢轴点不太可能恰好位于数组的中间，因此递归堆栈的深度可能略大于logN。我还没有做过数学计算，看看这个因素和上面描述的因素在算法复杂性中究竟扮演了多大的角色。

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

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

快速排序并不比归并排序好。对于O(n²)(很少发生的最坏情况)，快速排序可能比归并排序的O(nlogn)慢得多。快速排序的开销更小，所以对于小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)来实现这一点。

快速排序是一种就地排序算法，因此它更适合于数组。另一方面，归并排序需要额外的O(N)存储空间，更适合于链表。

与数组不同，在喜欢列表中，我们可以在中间插入O(1)空间和O(1)时间的项，因此归并排序中的归并操作可以在不需要任何额外空间的情况下实现。但是，为数组分配和取消分配额外空间会对归并排序的运行时间产生不利影响。归并排序也有利于链表，因为数据是按顺序访问的，没有太多的随机内存访问。

另一方面，快速排序需要大量的随机内存访问，而使用数组，我们可以直接访问内存，而不需要像链表那样进行任何遍历。同样，快速排序用于数组时具有良好的引用局部性，因为数组连续存储在内存中。

尽管这两种排序算法的平均复杂度都是O(NlogN)，但通常人们在执行普通任务时使用数组进行存储，因此快速排序应该是首选算法。

编辑:我刚刚发现归并排序最差/最好/平均情况总是nlogn，但快速排序可以从n2(最坏的情况下，元素已经排序)到nlogn(平均/最佳情况下，pivot总是将数组分为两半)。