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

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

正如许多人所注意到的，快速排序的平均情况性能要比归并排序快。但这只适用于假设按需访问任何内存段的时间为常数的情况。

在RAM中，这种假设通常不太坏(由于缓存的存在，这种假设并不总是正确的，但也不太坏)。然而，如果你的数据结构足够大，可以存储在磁盘上，那么快速排序就会因为磁盘平均每秒进行200次随机查找而被扼杀。但是，同样的磁盘在按顺序每秒读取或写入兆字节的数据方面没有任何问题。这正是归并排序所做的。

因此，如果数据必须在磁盘上排序，你真的，真的想使用归并排序的一些变体。(通常你快速排序子列表，然后开始将它们合并到某个大小阈值以上。)

Furthermore if you have to do anything with datasets of that size, think hard about how to avoid seeks to disk. For instance this is why it is standard advice that you drop indexes before doing large data loads in databases, and then rebuild the index later. Maintaining the index during the load means constantly seeking to disk. By contrast if you drop the indexes, then the database can rebuild the index by first sorting the information to be dealt with (using a mergesort of course!) and then loading it into a BTREE datastructure for the index. (BTREEs are naturally kept in order, so you can load one from a sorted dataset with few seeks to disk.)

在许多情况下，了解如何避免磁盘寻道使我将数据处理工作花费数小时而不是数天或数周。

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.

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

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

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

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

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

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

亩! 快速排序并不比归并排序更好，它非常适合于不同类型的应用。

归并排序是值得考虑的，如果速度是本质，糟糕的最差情况性能不能容忍，并且有额外的空间可用

你说他们«他们都是O(nlogn)[…]»。这是错误的。«快速排序使用大约n^2/2比较在最坏的情况下。

然而，根据我的经验，最重要的属性是在使用带有命令式范式的编程语言进行排序时，可以轻松实现顺序访问。

1 Sedgewick，算法