为什么quicksort比mergesort更好？

面试中我被问到了这个问题。 他们都是O（nlogn），但是大多数人使用Quicksort而不是Mergesort。 这是为什么？

Answer 1

Quicksort具有O（ n ² ）最差情况运行时间和O（ n log n ）平均情况运行时间。 然而，在许多情况下，它比合并sorting要优越，因为许多因素影响algorithm的运行时间，并且在将它们一起使用时，快速sorting胜出。

特别是，经常引用的sortingalgorithm的运行时间指的是执行sorting数据所需的比较次数或交换次数。 这确实是衡量性能的一个好方法，尤其是因为它独立于底层的硬件devise。 然而，其他的东西 – 比如引用的地方（也就是我们读了很多可能在caching中的元素吗？） – 在当前的硬件上也扮演着重要的angular色。 特别是Quicksort需要很less的额外空间，并且展现出良好的caching局部性，这使得它在许多情况下比合并sorting更快。

另外，通过使用适当select的关键点（例如随机选取）（这是一个很好的策略），几乎完全避免快速sorting的O（ n ² ）的最坏情况运行时间是非常容易的。

实际上，quicksort（特别是libstdc ++的std::sort ）的许多现代实现实际上是introsort ，其理论最坏情况是O（ n log n ），与合并sorting相同。 它通过限制recursion深度来实现这一点，并且一旦超过log n就切换到不同的algorithm（ heapsort ）。

Answer 2

正如许多人所指出的那样，quicksort的平均情况性能比mergesort更快。 但是，如果您假定按需访问任意一块内存的时间是固定的。

在RAM中，这个假设通常不会太糟（因为高速caching并不总是如此，但也不算太坏）。 但是，如果你的数据结构足够大，可以存放在磁盘上，那么快速sorting就会被平均磁盘每秒200次的随机查找所杀死 。 但是，同样的磁盘顺序读写每秒兆字节数据没有问题。 这正是mergesort所做的。

因此，如果数据必须在磁盘上sorting，你真的想在mergesort上使用一些变化。 （一般你快速排列子列表，然后开始将它们合并到一定的大小阈值以上。）

此外，如果您必须对这种大小的数据集进行任何操作 ，请仔细思考如何避免查找磁盘。 例如，这就是为什么标准build议是在数据库中执行大量数据加载之前删除索引，然后再重build索引。 在加载期间维护索引意味着不断的寻找磁盘。 相比之下，如果删除索引，那么数据库可以通过首先对要处理的信息进行sorting（当然使用合并），然后将其加载到索引的BTREE数据结构中来重build索引。 （BTREE自然保持顺序，所以你可以从一个sorting的数据集加载一个很less的search到磁盘。）

有很多场合，如何理解如何避免磁盘寻道，使我的数据处理工作需要几个小时，而不是几天或几周。

Answer 3

其实QuickSort是O（n ² ）。 它的平均运行时间是O（nlog（n）），但是最坏的情况是O（n ² ），当在包含less量唯一项的列表上运行时会发生这种情况。 随机化需要O（n）。 当然，这并没有改变最坏的情况，它只是防止恶意用户sorting需要很长时间。

QuickSort更受欢迎，因为它：

1. 就地（MergeSort需要额外的内存线性与要sorting的元素的数量）。
2. 有一个隐藏的小常量。

Answer 4

animationsortingalgorithm在4个不同的初始条件（随机的，几乎sorting的，颠倒的，很less的独特的）上显示了一些algorithm，并可能有所帮助。

Answer 5

“但是大多数人使用Quicksort而不是Mergesort，为什么？

一个没有给出的心理原因就是Quicksort更加巧妙地命名。 即良好的营销。

是的，使用三重分区的Quicksort可能是最好的通用sortingalgorithm之一，但是没有超越“快速”sorting听起来比“合并”sorting更强大的事实。

Answer 6

正如其他人所指出的，Quicksort的最坏情况是O（n ^ 2），而mergesort和heapsort停留在O（nlogn）。 但平均情况下，三者都是O（nlogn）。 所以绝大多数情况下都是可比的。

是什么让Quicksort平均更好的是，内循环意味着比较几个值与一个单一的，而另外两个条款是不同的每一个比较。 换句话说，Quicksort的读取数量是其他两种algorithm的一半。 在现代CPU上，性能受到访问时间的严重影响，所以最终Quicksort成为首选。

Answer 7

我想补充一下目前提到的三种algorithm（mergesort，quicksort和heapsorting），只有mergesort是稳定的。 也就是说，对于具有相同密钥的那些值，顺序不会改变。 在某些情况下，这是可取的。

但是，事实是，在实际情况下，大多数人只需要良好的平均performance和quicksort是…快=）

各种algorithm都有其起伏。 请参阅维基百科文章中的sortingalgorithm以获得良好的概述。

Answer 8

从Quicksort上的维基百科条目 ：

Quicksort还与mergesort竞争，这是另一种recursionsortingalgorithm，但是具有最坏情况Θ（nlogn）运行时间的好处。 Mergesort是一个稳定的sorting，不像quicksort和heapsort，可以很容易地适应链接列表和非常大的列表存储在缓慢访问的媒体，如磁盘存储或networking附加存储。 虽然可以编写快速sorting来对链表进行操作，但是它往往会遇到无法随意访问的枢轴select。 mergesort的主要缺点是，在数组上操作时，在最好的情况下需要Θ（n）辅助空间，而具有就地分区和尾recursion的快速sorting的变体仅使用Θ（logn）空间。 （请注意，在链接列表上操作时，mergesort只需要一个小的，恒定数量的辅助存储。）

Answer 9

亩！ Quicksort并不是更好，它比mergesort更适合不同types的应用程序。

Mergesort是值得考虑的，如果速度是关键，不好的最坏情况的performance是不能容忍的，并且有额外的空间。 1

你说他们都是O（nlogn）[…]»。 这是错误的。 在最坏的情况下，Quicksort使用了大约n ^ 2/2的比较。

然而根据我的经验，最重要的属性是顺序访问的简单实现，当使用编程语言进行sorting时，可以使用顺序访问。

1 Sedgewick，algorithm

Answer 10

快速sorting是实践中最快的sortingalgorithm，但有一些病态的情况，可以使其performance不如O（n2）。

Heapsort保证在O（n * ln（n））中运行，并且只需要有限的附加存储。 但是有很多真实世界testing的引用表明，heapsort比quicksort平均要慢很多。

Answer 11

维基百科的解释是：

通常，快速sorting在实践中比其他Θ（nlogn）algorithm快得多，因为其内部循环可以在大多数架构上有效地实现，并且在大多数现实世界的数据中，可以做出使得需要二次时间的概率最小化的deviseselect。

快速sorting

归并

我认为也存在快速sorting实现所不具备的Mergesort（即Ω（n））所需存储量的问题。 在最坏的情况下，它们algorithm时间相同，但合并需要更多的存储空间。

Answer 12

Quicksort并不比mergesort好。 对于O（n ^ 2）（很less发生的最坏情况），快速sorting可能比合并sorting的O（nlogn）慢得多。 Quicksort的开销较小，所以对于小型电脑和慢速电脑，效果会更好。 但是今天电脑的速度如此之快，以至于合并器的额外开销可以忽略不计，在大多数情况下，非常缓慢的快速sorting的风险远远超过合并器的微不足道的开销。

另外，mergesort会以原始顺序留下具有相同键的项目，这是一个有用的属性。

Answer 13

我想补充一些关于QuickSort如何与最佳情况分歧的有效math方法，以及我希望能够帮助人们更好地理解O（n ^ 2）情况为何不是真实的关注QuickSort更复杂的实现。

在随机访问问题之外，影响QuickSort性能的主要因素有两个，它们都与数据透视如何与正在sorting的数据相比较。

1）数据中的less量密钥。 所有相同值的数据集将在一个香草2分区快速sorting中按n ^ 2次sorting，因为除了枢轴位置以外的所有值每次都放置在一侧。 现代实现通过诸如使用3分区sorting的方法来解决这个问题。 这些方法在O（n）时间内对所有相同值的数据集执行。 所以使用这种实现意味着具有less量密钥的input实际上改进了性能时间并且不再是关注的问题。

2）极差的枢轴select会导致最坏的情况下的性能。 在理想的情况下，数据枢轴将始终保持50％的数据更小，50％的数据更大，从而使input在每次迭代过程中都被分解成一半。 这给了我们n个比较和交换时间log-2（n）recursionO（n * logn）时间。

非理想数据透视select会影响执行时间多less？

让我们考虑一个一致的select数据的75％的数据是在一侧的枢轴的情况下。 它仍然是O（n * logn），但现在日志的基础已经改变为1 / 0.75或1.33。 当改变base时的性能关系总是由log（2）/ log（newBase）表示的常量。 在这种情况下，这个常数是2.4。 所以这个枢轴select的质量要比理想的长2.4倍。

这有多快？

不是很快，直到枢轴select（一贯）非常糟糕：

• 一方50％:(理想情况下）
• 75％一方：2.4倍
• 90％一方：6.6倍
• 一方95％，13.5倍
• 一方99％，69倍

当我们接近100％时，执行的日志部分接近n，整个执行渐近接近O（n ^ 2）。

在QuickSort的一个天真的实现中，诸如sorting数组（对于第一个元素枢轴）或反向sorting数组（对于最后一个元素枢轴）的情况将可靠地产生最坏情况的O（n ^ 2）执行时间。 另外，具有可预测枢轴select的实施可以受到旨在产生最坏情况执行的数据的DoS攻击。 现代实现通过多种方法来避免这种情况，例如在sorting之前对数据进行随机化，select3个随机select的索引的中值等等。在这种随机化中，我们有两种情况：

• 小数据集。 最坏的情况是合理可能的，但是O（n ^ 2）不是灾难性的，因为n足够小，n ^ 2也是小的。
• 大数据集。 最坏的情况在理论上是可能的，但不是在实践中。

我们有多可能看到可怕的performance？

机会是微乎其微的 。 我们来考虑一下5000个值：

我们假设的实现将使用3个随机select的索引的中值select一个数据透视表。 我们将考虑在25％-75％范围内为“好”的枢轴，以及在0％-25％或75％-100％范围内为“坏”的枢轴。 如果使用3个随机指数的中值来查看概率分布，则每个recursion有11/16的机会以良好的支点结束。 让我们做两个保守的（和错误的）假设来简化math：

1. 良好的枢轴总是在25％/ 75％的分割，并在2.4 *的理想情况下运作。 我们从来没有得到一个理想的分裂或任何分裂比25/75更好。

2. 糟糕的枢轴总是最坏的情况，对解决scheme没有任何贡献。

我们的QuickSort实现将在n = 10处停止，并切换到插入sorting，因此我们需要22个25％/ 75％的数据透视分区，以打破目前为止的5000个input值。 （10 * 1.333333 ^ 22> 5000）或者，我们需要4990个最差情况支点。 请记住，如果我们在任何时候累积了22个良好的支点，那么sorting将完成，所以最坏的情况或任何附近的东西都需要非常糟糕的运气。 如果我们用88个recursion实际实现了将n = 10所需的22个好的支点，那么理想情况下就是4 * 2.4 *或大约10倍的执行时间。 在88次recursion之后，我们有可能达不到所需的22个良好的枢纽？

二项概率分布可以回答这个问题，答案是10 ^ -18左右。 （n是88，k是21，p是0.6875）你的用户在点击[SORT]所需的1秒内被雷击的可能性大约是千分之一，比10 *理想的情况。 数据越大，这个机会越小。 下面是一些数组大小和相应的运行时间超过10 *理想的机会：

• 640个项目的数组：10 ^ -13（在60次尝试中需要15个良好的支点）
• 5000个物品的arrays：10 ^ -18（88次尝试中需要22个良好的枢轴）
• 40,000个物品的arrays：10 ^ -23（需要在116个中有29个好的支点）

请记住，这是2个保守的假设，比现实更糟。 所以实际performance比较好，剩余概率的平衡比不接近理想。

最后，正如其他人所提到的，即使这些荒谬的不太可能的情况可以通过切换到堆sorting来消除，如果recursion堆栈太深。 所以TLDR是，为了实现QuickSort的良好实现，最坏的情况并不存在，因为它已经被devise出来并且在O（n * logn）时间内完成执行。

Answer 14

答案会稍微倾向于使用DualPivotQuickSort为原始值带来的更改。 它在JAVA 7中用于在java.util.Arrays中进行sorting

 It is proved that for the Dual-Pivot Quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively. Full mathematical proof see in attached proof.txt and proof_add.txt files. Theoretical results are also confirmed by experimental counting of the operations. 

你可以在这里findJAVA7 implmentation – http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

关于DualPivotQuickSort更多真棒阅读 – http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Answer 15

虽然他们都在相同的复杂类，但这并不意味着他们都有相同的运行时间。 Quicksort通常比mergesort更快，仅仅是因为编写紧密的实现比较容易，而且它所做的操作可以更快。 这是因为快速sorting速度通常更快，人们用它来代替mergesort。

然而！ 我个人经常会使用mergesort或quicksort变种退化mergesort时，quicksort做得不好。 记得。 Quicksort 平均只有O（n log n）。 最坏的情况是O（n ^ 2）！ Mergesort总是O（n log n）。 如果实时性能或响应能力是必须的，并且您的input数据可能来自恶意来源，则不应使用简单快速sorting。

Answer 16

Quicksort具有更好的平均情况复杂性，但在某些应用中，这是错误的select。 快速sorting容易受到拒绝服务攻击。 如果攻击者可以selectinput进行sorting，他可以很容易地构造一个集合，其中o（n ^ 2）的时间复杂度最差。

Mergesort的平均情况复杂度和最坏情况下的复杂度是相同的，因此不会遇到同样的问题。 合并sorting的这一特性也使其成为实时系统的最佳select – 正是因为没有病态的情况导致运行速度慢得多。

因为这些原因，我是Mergesort的粉丝，而不是Quicksort。

Answer 17

所有的事情都是平等的，我希望大多数人能够使用最方便的方式，而且这种方法往往是qsort（3）。 除此之外，quicksort在数组上是非常快的，就像mergesort是列表的常用select一样。

我想知道的是为什么看到基数或桶sorting是非常罕见的。 它们是O（n），至less在链表上，它只需要将密钥转换成序号。 （string和浮动工作正常。）

我在想，这个原因与计算机科学的教学有关。 我甚至不得不在演algorithm分析中向演讲者certificate，确实有可能比O（n log（n））更快地sorting。 （他有证据certificate你比O（n log（n））更快的sorting，这是真的。）

在其他消息中，浮点数可以按整数sorting，但是之后必须将负数转换。

编辑：其实，这是一个更加恶毒的方法来sorting浮动整数： http : //www.stereopsis.com/radix.html 。 请注意，无论使用什么sortingalgorithm，都可以使用翻转技巧。

Answer 18

这很难说。最差的MergeSort是n（log2n）-n + 1，如果n等于2 ^ k（我已经certificate了这一点），这是准确的。对于任何n，它在（n lg n – n + 1）和（n lg n + n + O（lg n）），但对于quickSort，最好是nlog2n（也等于2 ^ k）。如果用quickSort分割Mergesort，当n是无穷大时，它等于1。就好像MergeSort最糟糕的情况比QuickSort最好的情况好，为什么我们要使用quicksort？但是请记住，MergeSort不在位，它需要2n memeroy空间。而且MergeSort也需要做很多的数组拷贝，不包括在algorithm的分析中。总之，MergeSort真的比速度快，但实际上你需要考虑memeory空间，数组拷贝，合并的成本慢于快速sorting。我曾经做过实验在Java中被Random类给了1000000个数字，并且合并了2610ms，快速排列了1370ms。

Answer 19

为什么Quicksort好？

• QuickSort在最坏情况下和NlogN平均情况下取N ^ 2。 数据sorting时发生最坏的情况。 在分类开始之前，可以通过随机洗牌来缓解这个问题。
• QuickSort不会占用合并sorting所带来的额外内存。
• 如果数据集很大，并且有相同的项目，则使用3路分区可以减lessQuicksort的复杂度。 更多的相同的项目没有更好的sorting。 如果所有项目都是相同的，则按线性时间sorting。 [这是大多数图书馆的默认实现]

Quicksort总是比Mergesort更好吗？

不是真的。

• Mergesort是稳定的，但Quicksort不是。 所以如果你需要输出的稳定性，你可以使用Mergesort。 在许多实际应用中需要稳定性。
• 内存现在便宜。 因此，如果Mergesort使用的额外内存对您的应用程序不是至关重要的，那么使用Mergesort并没有什么坏处。

注意：在java中，Arrays.sort（）函数对原始数据types使用Quicksort，对象数据types使用Mergesort。 由于对象消耗内存开销，因此为Mergesort添加一点开销可能不会成为性能angular度的任何问题。

参考 ：观看Coursera的普林斯顿algorithm课程第3周的QuickSortvideo

Answer 20

快速sorting是最坏的情况O（n ^ 2），然而，平均情况一贯地执行合并sorting。 每个algorithm都是O（nlogn），但是您需要记住，在谈论Big O时，我们忽略了较低的复杂性因素。 当涉及到常数因素时，快速sorting比合并sorting有了显着的改进。

合并sorting也需要O（2n）内存，而快速sorting可以在适当位置完成（只需要O（n））。 这是快速sorting通常优于合并sorting的另一个原因。

额外信息：

快速sorting最糟糕的情况发生在枢轴select不当时。 考虑下面的例子：

[5，4，3，2，1]

如果主键select为组中最小或最大的数字，则快速sorting将以O（n ^ 2）运行。 select列表中最大或最小25％的元素的概率是0.5。 这给了algorithm一个0.5的机会成为一个很好的支点。 如果我们使用一个典型的枢轴selectalgorithm（比如说select一个随机元素），那么我们有0.5个机会为每一个枢轴的selectselect一个好的枢轴。 对于一个大尺寸的集合，总是select一个不好的支点的概率是0.5 * n。 基于这个概率，快速sorting对于平均（和典型）情况是有效的。

Answer 21

与合并sorting不同，快速sorting不使用辅助空间。 而合并sorting使用辅助空间O（n）。 但是，合并sorting的最坏情况下的时间复杂度为O（nlogn），而快速sorting的最坏情况下的复杂度是O（n ^ 2），这是在数组已经sorting时发生的。

Answer 22

快速vs合并sorting的小增加。

也可以依靠种类的分类项目。 如果访问项目，交换和比较不是简单的操作，比如在平面内存中比较整数，那么合并sorting可以是更好的algorithm。

例如，我们使用远程服务器上的networking协议对项目进行sorting。

而且，在像“链接列表”这样的自定义容器中，快速sorting没有任何好处。
1.在链表上合并sorting，不需要额外的内存。 2.在快速sorting中访问元素不是顺序的（在内存中）

Answer 23

在合并sorting中，一般algorithm是：

1. sorting左侧的子数组
2. sorting正确的子数组
3. 合并2个sorting的子数组

在顶层，合并2个sorting的子数组涉及到处理N个元素。

低于这个水平，第三步的每一次迭代都涉及到处理N / 2个元素，但是你必须重复这个过程两次。 所以你还在处理2 * N / 2 == N的元素。

One level below that, you're merging 4 * N/4 == N elements, and so on. Every depth in the recursive stack involves merging the same number of elements, across all calls for that depth.

Consider the quick-sort algorithm instead:

1. Pick a pivot point
2. Place the pivot point at the correct place in the array, with all smaller elements to the left, and larger elements to the right
3. Sort the left-subarray
4. Sort the right-subarray

At the top level, you're dealing with an array of size N. You then pick one pivot point, put it in its correct position, and can then ignore it completely for the rest of the algorithm.

One level below that, you're dealing with 2 sub-arrays that have a combined size of N-1 (ie, subtract the earlier pivot point). You pick a pivot point for each sub-array, which comes up to 2 additional pivot points.

One level below that, you're dealing with 4 sub-arrays with combined size N-3, for the same reasons as above.

Then N-7… Then N-15… Then N-32…

The depth of your recursive stack remains approximately the same (logN). With merge-sort, you're always dealing with a N-element merge, across each level of the recursive stack. With quick-sort though, the number of elements that you're dealing with diminishes as you go down the stack. For example, if you look at the depth midway through the recursive stack, the number of elements you're dealing with is N – 2^((logN)/2)) == N – sqrt(N).

Disclaimer: On merge-sort, because you divide the array into 2 exactly equal chunks each time, the recursive depth is exactly logN. On quick-sort, because your pivot point is unlikely to be exactly in the middle of the array, the depth of your recursive stack may be slightly greater than logN. I haven't done the math to see how big a role this factor and the factor described above, actually play in the algorithm's complexity.

Answer 24

When I experimented with both sorting algorithms, by counting the number of recursive calls, quicksort consistently has less recursive calls than mergesort. It is because quicksort has pivots, and pivots are not included in the next recursive calls. That way quicksort can reach recursive base case more quicker than mergesort.

Answer 25

Something to consider is memory as well. Mergesort requires an additional array, say a "workspace array". If your memory is barely big enough to store your original array, then mergesort will not work.

Answer 26

Quick sort is an in-place sorting algorithm, so its better suited for arrays. Merge sort on the other hand requires extra storage of O(N), and is more suitable for linked lists.

Unlike arrays, in liked list we can insert items in the middle with O(1) space and O(1) time, therefore the merge operation in merge sort can be implemented without any extra space. However, allocating and de-allocating extra space for arrays have an adverse effect on the run time of merge sort. Merge sort also favors linked list as data is accessed sequentially, without much random memory access.

Quick sort on the other hand requires a lot of random memory access and with an array we can directly access the memory without any traversing as required by linked lists. Also quick sort when used for arrays have a good locality of reference as arrays are stored contiguously in memory.

Even though both sorting algorithms average complexity is O(NlogN), usually people for ordinary tasks uses an array for storage, and for that reason quick sort should be the algorithm of choice.

EDIT: I just found out that merge sort worst/best/avg case is always nlogn, but quick sort can vary from n2(worst case when elements are already sorted) to nlogn(avg/best case when pivot always divides the array in two halves).

Answer 27

This is a pretty old question, but since I've dealt with both recently here are my 2c:

Merge sort needs on average ~ N log N comparisons. For already (almost) sorted sorted arrays this gets down to 1/2 N log N, since while merging we (almost) always select "left" part 1/2 N of times and then just copy right 1/2 N elements. Additionally I can speculate that already sorted input makes processor's branch predictor shine but guessing almost all branches correctly, thus preventing pipeline stalls.

Quick sort on average requires ~ 1.38 N log N comparisons. It does not benefit greatly from already sorted array in terms of comparisons (however it does in terms of swaps and probably in terms of branch predictions inside CPU).

My benchmarks on fairly modern processor shows the following:

When comparison function is a callback function (like in qsort() libc implementation) quicksort is slower than mergesort by 15% on random input and 30% for already sorted array for 64 bit integers.

On the other hand if comparison is not a callback, my experience is that quicksort outperforms mergesort by up to 25%.

However if your (large) array has a very few unique values, merge sort starts gaining over quicksort in any case.

So maybe the bottom line is: if comparison is expensive (eg callback function, comparing strings, comparing many parts of a structure mostly getting to a second-third-forth "if" to make difference) – the chances are that you will be better with merge sort. For simpler tasks quicksort will be faster.

That said all previously said is true: – Quicksort can be N^2, but Sedgewick claims that a good randomized implementation has more chances of a computer performing sort to be struck by a lightning than to go N^2 – Mergesort requires extra space

Answer 28

In c/c++ land, when not using stl containers, I tend to use quicksort, because it is built into the run time, while mergesort is not.

So I believe that in many cases, it is simply the path of least resistance.

In addition performance can be much higher with quick sort, for cases where the entire dataset does not fit into the working set.