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

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

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

正如其他人所注意到的，快速排序的最坏情况是O(n²)，而归并排序和堆排序则停留在O(nlogn)。然而，在平均情况下，这三个都是O(nlogn);所以它们在大多数情况下是可比较的。

平均而言，快速排序更好的地方在于，内循环意味着将多个值与单个值进行比较，而在其他两个循环中，每次比较时两个项都是不同的。换句话说，Quicksort的读取次数是其他两种算法的一半。在现代cpu上，访问时间在很大程度上决定了性能，因此快速排序最终成为一个很好的首选。

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

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

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

与归并排序不同，快速排序不使用辅助空间。而归并排序使用辅助空间O(n)。 归并排序的最坏情况时间复杂度是O(nlogn)而快速排序的最坏情况复杂度是O(n²)这发生在数组已经排序的时候。

快速排序是在实践中最快的排序算法，但有一些病态的情况，可以使它的表现差到O(n2)。

堆排序保证在O(n*ln(n))中运行，并且只需要有限的额外存储空间。但是有许多真实世界的测试表明堆排序比快速排序平均要慢得多。

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

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

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

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