但大多数人使用快速排序而不是归并排序。为什么呢?”

一个没有给出的心理学原因是，快速排序的名字更为巧妙。很好的市场营销。

是的，带有三重分区的快速排序可能是最好的通用排序算法之一，但“快速”排序听起来比“归并”排序强大得多，这是无法克服的事实。

快速排序和合并排序的小增加。

它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作，就像比较平面内存中的整数一样，那么归并排序可能是更可取的算法。

例如，我们在远程服务器上使用网络协议对项目进行排序。

而且，在像“链表”这样的自定义容器中，也没有快速排序的好处。 1. 对链表进行归并排序，不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)

快速排序并不比归并排序好。对于O(n²)(很少发生的最坏情况)，快速排序可能比归并排序的O(nlogn)慢得多。快速排序的开销更小，所以对于小n和速度较慢的计算机，它会更好。但是今天的计算机是如此之快，以至于合并排序的额外开销可以忽略不计，并且在大多数情况下，非常慢的快速排序的风险远远超过合并排序的微不足道的开销。

此外，归并排序将具有相同键的项按原始顺序保留，这是一个有用的属性。

One of the reason is more philosophical. Quicksort is Top->Down philosophy. With n elements to sort, there are n! possibilities. With 2 partitions of m & n-m which are mutually exclusive, the number of possibilities go down in several orders of magnitude. m! * (n-m)! is smaller by several orders than n! alone. imagine 5! vs 3! *2!. 5! has 10 times more possibilities than 2 partitions of 2 & 3 each . and extrapolate to 1 million factorial vs 900K!*100K! vs. So instead of worrying about establishing any order within a range or a partition,just establish order at a broader level in partitions and reduce the possibilities within a partition. Any order established earlier within a range will be disturbed later if the partitions themselves are not mutually exclusive.

任何自下而上的排序方法，如归并排序或堆排序，就像工人或雇员的方法一样，人们很早就开始在微观层面进行比较。但是，一旦在它们之间发现了一个元素，这个顺序就必然会丢失。这些方法非常稳定和可预测，但要做一定量的额外工作。

Quick Sort is like Managerial approach where one is not initially concerned about any order , only about meeting a broad criterion with No regard for order. Then the partitions are narrowed until you get a sorted set. The real challenge in Quicksort is in finding a partition or criterion in the dark when you know nothing about the elements to sort. That is why we either need to spend some effort to find a median value or pick 1 at random or some arbitrary "Managerial" approach . To find a perfect median can take significant amount of effort and leads to a stupid bottom up approach again. So Quicksort says just a pick a random pivot and hope that it will be somewhere in the middle or do some work to find median of 3 , 5 or something more to find a better median but do not plan to be perfect & don't waste any time in initially ordering. That seems to do well if you are lucky or sometimes degrades to n^2 when you don't get a median but just take a chance. Any way data is random. right. So I agree more with the top ->down logical approach of quicksort & it turns out that the chance it takes about pivot selection & comparisons that it saves earlier seems to work better more times than any meticulous & thorough stable bottom ->up approach like merge sort. But

这是一个相当老的问题，但因为我最近处理了这两个问题，所以这里是我的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)存储空间，更适合于链表。

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

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

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

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