我在一次面试中被问到这个问题。它们都是O(nlogn)，但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
快速排序是最坏情况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.
其他回答
虽然它们都在相同的复杂度类中，但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快，因为它更容易编写紧凑的实现代码，它所做的操作也更快。这是因为快速排序通常更快，人们使用它而不是归并排序。
然而!我个人经常会使用归并排序或快速排序变体，当快速排序表现不佳时，它们会降级为归并排序。记住。快速排序平均只有O(n log n)最坏情况是O(n²)归并排序总是O(n log n).在实时性能或响应性是必须的情况下，你的输入数据可能来自恶意来源，你不应该使用简单的快速排序。
快速排序和合并排序的小增加。
它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作，就像比较平面内存中的整数一样，那么归并排序可能是更可取的算法。
例如，我们在远程服务器上使用网络协议对项目进行排序。
而且，在像“链表”这样的自定义容器中，也没有快速排序的好处。 1. 对链表进行归并排序，不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)
正如其他人所注意到的，快速排序的最坏情况是O(n²)，而归并排序和堆排序则停留在O(nlogn)。然而，在平均情况下，这三个都是O(nlogn);所以它们在大多数情况下是可比较的。
平均而言，快速排序更好的地方在于，内循环意味着将多个值与单个值进行比较，而在其他两个循环中，每次比较时两个项都是不同的。换句话说，Quicksort的读取次数是其他两种算法的一半。在现代cpu上，访问时间在很大程度上决定了性能，因此快速排序最终成为一个很好的首选。
但大多数人使用快速排序而不是归并排序。为什么呢?”
一个没有给出的心理学原因是，快速排序的名字更为巧妙。很好的市场营销。
是的，带有三重分区的快速排序可能是最好的通用排序算法之一，但“快速”排序听起来比“归并”排序强大得多，这是无法克服的事实。
快速排序是最坏情况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.
