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

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

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

快速排序是最坏情况O(n²)，然而，平均情况始终执行归并排序。每个算法都是O(nlogn)，但你需要记住，当谈论大O时，我们忽略了较低的复杂度因素。当涉及到常数因子时，快速排序比归并排序有显著的改进。

归并排序也需要O(2n)内存，而快速排序可以就地完成(只需要O(n))。这是快速排序通常比归并排序更受欢迎的另一个原因。

额外信息:

快速排序的最坏情况发生在枢轴选择不佳时。考虑下面的例子:

[5, 4, 3, 2, 1]

If the pivot is chosen as the smallest or largest number in the group then quick sort will run in O(n^2). The probability of choosing the element that is in the largest or smallest 25% of the list is 0.5. That gives the algorithm a 0.5 chance of being a good pivot. If we employ a typical pivot choosing algorithm (say choosing a random element), we have 0.5 chance of choosing a good pivot for every choice of a pivot. For collections of a large size the probability of always choosing a poor pivot is 0.5 * n. Based on this probability quick sort is efficient for the average (and typical) case.

维基百科的解释是:

通常，快速排序在实践中比其他Θ(nlogn)算法要快得多，因为它的内部循环可以在大多数架构上有效地实现，并且在大多数现实数据中，可以做出设计选择，使需要二次时间的概率最小化。

快速排序

Mergesort

我认为归并排序(即Ω(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.)

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

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

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

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