首先，在发布此问题之前，我已经完成了搜索。我已经看过Why is quicksort better than mergesort?处的问题，但它有一些矛盾的答案。
根据我的观察，人们说quicksort比mergesort更快，因为它的引用位置，缓存命中率等。现在，我接受这在实践中很重要，但我的问题纯粹是关于分析-我对递归不感兴趣开销，缓存问题等。此外，答案通常不清楚他们说得更快时的含义，我不确定他们是否指的是执行时间，因此不确定缓存问题是否与答案有关。
无论如何，我的问题很简单。纯粹就执行的比较而言，是否mergesort总是比quicksort更高效？维基百科告诉我是的，这是我一直想的，但正如我所说，其他人说的却不同。
最佳答案
在最坏的情况下，基本Quicksort将在O（n ^ 2）时间内运行。考虑是否所选的枢轴始终是下一个最小元素，它等效于插入排序。 Mergesort没有这个困难。
此外，Mergesort也是stable，这意味着它保留了相等值的元素的顺序（因此，对于“先按此排序，然后按该排序”排序是很有用的），而不是Quicksort。
Mergesort的最大缺点是，大多数实现必须使用2n空间完成，而Quicksort可以就地完成（以防应用程序出现空间问题）。
Quicksort和Mergesort上的各个Wikipedia都很出色，我建议阅读它们。
关于analysis - 在比较方面Quicksort vs Mergesort，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13096603/