我在一次面试中被问到这个问题。它们都是O(nlogn)，但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
但大多数人使用快速排序而不是归并排序。为什么呢?”
一个没有给出的心理学原因是，快速排序的名字更为巧妙。很好的市场营销。
是的，带有三重分区的快速排序可能是最好的通用排序算法之一，但“快速”排序听起来比“归并”排序强大得多，这是无法克服的事实。
其他回答
亩! 快速排序并不比归并排序更好，它非常适合于不同类型的应用。
归并排序是值得考虑的，如果速度是本质，糟糕的最差情况性能不能容忍，并且有额外的空间可用
你说他们«他们都是O(nlogn)[…]»。这是错误的。«快速排序使用大约n^2/2比较在最坏的情况下。
然而，根据我的经验，最重要的属性是在使用带有命令式范式的编程语言进行排序时，可以轻松实现顺序访问。
1 Sedgewick，算法
实际上，快速排序是O(n2)。它的平均情况运行时间是O(nlog(n))，但最坏情况是O(n2)，这发生在在包含很少唯一项的列表上运行时。随机化花费O(n)。当然，这并没有改变最坏的情况，它只是防止恶意用户使您的排序花费很长时间。
快速排序更受欢迎，因为它:
(MergeSort需要额外的内存，与要排序的元素数量成线性关系)。 有一个小的隐藏常数。
正如其他人所注意到的，快速排序的最坏情况是O(n²)，而归并排序和堆排序则停留在O(nlogn)。然而，在平均情况下，这三个都是O(nlogn);所以它们在大多数情况下是可比较的。
平均而言，快速排序更好的地方在于，内循环意味着将多个值与单个值进行比较，而在其他两个循环中，每次比较时两个项都是不同的。换句话说，Quicksort的读取次数是其他两种算法的一半。在现代cpu上，访问时间在很大程度上决定了性能，因此快速排序最终成为一个很好的首选。
快速排序具有更好的平均情况复杂度，但在某些应用中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入，他可以很容易地构造一个时间复杂度为o(n^2)的最坏情况的集合。
归并排序的平均情况复杂性和最坏情况复杂性是相同的，因此不会遇到相同的问题。归并排序的这一特性也使它成为实时系统的最佳选择——确切地说，因为没有导致它运行得非常非常慢的病理情况。
由于这些原因，我更喜欢归并排序，而不是快速排序。
快速排序和合并排序的小增加。
它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作，就像比较平面内存中的整数一样，那么归并排序可能是更可取的算法。
例如，我们在远程服务器上使用网络协议对项目进行排序。
而且，在像“链表”这样的自定义容器中，也没有快速排序的好处。 1. 对链表进行归并排序，不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)
