analysis - 快速排序与合并排序的比较

Question

首先，我在发布这个问题之前已经进行了搜索。我已经看过这个问题 Why is quicksort better than mergesort?但它有一些相互矛盾的答案。

根据我的观察，人们说快速排序比合并排序“更快”，因为它的引用位置、缓存命中等。现在，我承认这在实践中很重要，但我的问题纯粹是关于分析 - 我不是对递归开销、缓存问题等感兴趣。此外，当他们说更快时，答案通常很模糊，我不确定他们是否指的是执行所需的时间，因此缓存问题是否与他们的答案相关。

无论如何，我的问题很简单。纯粹就执行的比较次数而言，合并排序是否总是比快速排序更有效？维基百科告诉我是的，我一直这么认为，但正如我所说，其他人有不同的说法。

Answer 1

在最坏的情况下，基本快速排序将在 O(n^2) 时间内运行。考虑如果选择的主元总是下一个最小元素，则相当于插入排序。归并排序没有这个困难。

此外，归并排序也是 stable ，这意味着它保留了同等值元素的顺序(因此它有利于“先按这个，然后按那个”排序)，而快速排序则不然。

合并排序的最大缺点是大多数实现必须使用 2n 空间来完成，而快速排序可以就地完成(如果应用程序中存在空间问题)。

关于 Quicksort 的个人维基百科和 Mergesort非常好，我推荐阅读它们。