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

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.)

这是一个相当老的问题，但因为我最近处理了这两个问题，所以这里是我的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 —归并排序需要占用额外空间

我想补充的是，到目前为止提到的三种算法(归并排序，快速排序和堆排序)只有归并排序是稳定的。也就是说，对于那些具有相同键的值，顺序不会改变。在某些情况下，这是可取的。

但是，说实话，在实际情况下，大多数人只需要良好的平均性能和快速排序…快速=)

所有排序算法都有其起伏。有关排序算法的概述，请参阅维基百科的文章。

That's hard to say.The worst of MergeSort is n(log2n)-n+1,which is accurate if n equals 2^k(I have already proved this).And for any n,it's between (n lg n - n + 1) and (n lg n + n + O(lg n)).But for quickSort,its best is nlog2n(also n equals 2^k).If you divide Mergesort by quickSort,it equals one when n is infinite.So it's as if the worst case of MergeSort is better than the best case of QuickSort,why do we use quicksort?But remember,MergeSort is not in place,it require 2n memeroy space.And MergeSort also need to do many array copies,which we don't include in the analysis of algorithm.In a word,MergeSort is really faseter than quicksort in theroy,but in reality you need to consider memeory space,the cost of array copy,merger is slower than quick sort.I once made an experiment where I was given 1000000 digits in java by Random class,and it took 2610ms by mergesort,1370ms by quicksort.

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

这是采访中经常被问到的一个问题，尽管归并排序在最坏情况下性能更好，但快速排序被认为比归并排序更好，特别是对于大输入。以下是快速排序更好的原因:

1-辅助空间:快速排序是一种就地排序算法。就地排序意味着执行排序不需要额外的存储空间。另一方面，归并排序需要一个临时数组来归并已排序的数组，因此它并不到位。

2-最坏情况:快速排序O(n^2)的最坏情况可以通过使用随机化快速排序来避免。通过选择正确的枢轴，可以很容易地避免这种情况。通过选择合适的枢轴元来获得平均情况下的行为，从而提高了算法的性能，达到了与归并排序一样的效率。

3-引用的局部性:快速排序特别展示了良好的缓存局部性，这使得它在许多情况下比归并排序更快，比如在虚拟内存环境中。

4-尾递归:快速排序是尾递归，而归并排序不是。尾递归函数是一种函数，其中递归调用是函数执行的最后一件事。尾递归函数被认为比非尾递归函数更好，因为尾递归可以被编译器优化。