That's hard to say.The worst of MergeSort is n(log2n)-n+1,which is accurate if n equals 2^k(I have already proved this).And for any n,it's between (n lg n - n + 1) and (n lg n + n + O(lg n)).But for quickSort,its best is nlog2n(also n equals 2^k).If you divide Mergesort by quickSort,it equals one when n is infinite.So it's as if the worst case of MergeSort is better than the best case of QuickSort,why do we use quicksort?But remember,MergeSort is not in place,it require 2n memeroy space.And MergeSort also need to do many array copies,which we don't include in the analysis of algorithm.In a word,MergeSort is really faseter than quicksort in theroy,but in reality you need to consider memeory space,the cost of array copy,merger is slower than quick sort.I once made an experiment where I was given 1000000 digits in java by Random class,and it took 2610ms by mergesort,1370ms by quicksort.

快速排序和合并排序的小增加。

它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作，就像比较平面内存中的整数一样，那么归并排序可能是更可取的算法。

例如，我们在远程服务器上使用网络协议对项目进行排序。

而且，在像“链表”这样的自定义容器中，也没有快速排序的好处。 1. 对链表进行归并排序，不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)

That's hard to say.The worst of MergeSort is n(log2n)-n+1,which is accurate if n equals 2^k(I have already proved this).And for any n,it's between (n lg n - n + 1) and (n lg n + n + O(lg n)).But for quickSort,its best is nlog2n(also n equals 2^k).If you divide Mergesort by quickSort,it equals one when n is infinite.So it's as if the worst case of MergeSort is better than the best case of QuickSort,why do we use quicksort?But remember,MergeSort is not in place,it require 2n memeroy space.And MergeSort also need to do many array copies,which we don't include in the analysis of algorithm.In a word,MergeSort is really faseter than quicksort in theroy,but in reality you need to consider memeory space,the cost of array copy,merger is slower than quick sort.I once made an experiment where I was given 1000000 digits in java by Random class,and it took 2610ms by mergesort,1370ms by quicksort.

快速排序有O(n2)最差情况运行时和O(nlogn)平均情况运行时。然而，在许多情况下，它优于归并排序，因为许多因素影响算法的运行时，并且，当把它们放在一起时，快速排序胜出。

In particular, the often-quoted runtime of sorting algorithms refers to the number of comparisons or the number of swaps necessary to perform to sort the data. This is indeed a good measure of performance, especially since it’s independent of the underlying hardware design. However, other things – such as locality of reference (i.e. do we read lots of elements which are probably in cache?) – also play an important role on current hardware. Quicksort in particular requires little additional space and exhibits good cache locality, and this makes it faster than merge sort in many cases.

此外，通过使用适当的枢轴选择，几乎完全避免快速排序的最坏情况运行时间O(n2)是非常容易的——比如随机选择它(这是一个很好的策略)。

在实践中，许多现代的快速排序实现(特别是libstdc++的std::sort)实际上是introsort，其理论上的最差情况是O(nlogn)，与归并排序相同。它通过限制递归深度，并在超过logn时切换到不同的算法(heapsort)来实现这一点。

答案将略微倾向于快速排序w.r.t的变化带来的DualPivotQuickSort的基本值。它在JAVA 7中用于在JAVA .util. arrays中排序

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.

您可以在这里找到JAVA7实现- 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

在所有条件相同的情况下，我希望大多数人使用最方便的方法，这往往是qsort(3)。除此之外，快速排序在数组上非常快，就像归并排序是列表的常用选择一样。

我想知道的是为什么基数排序和桶排序这么少见。它们是O(n)至少在链表上是这样的它所需要的只是将键转换为序数的方法。(字符串和浮动工作得很好。)

我认为原因与计算机科学的教学方式有关。我甚至不得不向我的讲师演示算法分析，它确实有可能比O(nlog (n))更快地排序。(他证明了比较排序不能比O(nlog (n))快，这是正确的)

在其他新闻中，浮点数可以按整数排序，但之后必须将负数反转。

编辑: 实际上，这里有一种更糟糕的将浮点数作为整数排序的方法:http://www.stereopsis.com/radix.html。注意，不管你实际使用什么排序算法，比特翻转技巧都可以使用……