快速排序是在实践中最快的排序算法，但有一些病态的情况，可以使它的表现差到O(n2)。

堆排序保证在O(n*ln(n))中运行，并且只需要有限的额外存储空间。但是有许多真实世界的测试表明堆排序比快速排序平均要慢得多。

快速排序并不比归并排序好。对于O(n²)(很少发生的最坏情况)，快速排序可能比归并排序的O(nlogn)慢得多。快速排序的开销更小，所以对于小n和速度较慢的计算机，它会更好。但是今天的计算机是如此之快，以至于合并排序的额外开销可以忽略不计，并且在大多数情况下，非常慢的快速排序的风险远远超过合并排序的微不足道的开销。

此外，归并排序将具有相同键的项按原始顺序保留，这是一个有用的属性。

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

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

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

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

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

快速排序具有更好的平均情况复杂度，但在某些应用中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入，他可以很容易地构造一个时间复杂度为o(n^2)的最坏情况的集合。

归并排序的平均情况复杂性和最坏情况复杂性是相同的，因此不会遇到相同的问题。归并排序的这一特性也使它成为实时系统的最佳选择——确切地说，因为没有导致它运行得非常非常慢的病理情况。

由于这些原因，我更喜欢归并排序，而不是快速排序。

同时考虑时间和空间的复杂性。 归并排序: 时间复杂度:O(nlogn)， 空间复杂度:O(nlogn)

快速排序: 时间复杂度:O(n²)， 空间复杂度:O(n)

现在，他们各自在一个场景中获胜。 但是，使用随机枢轴，您几乎总是可以将快速排序的时间复杂度降低到O(nlogn)。

因此，在许多应用中，快速排序是首选，而不是归并排序。

为什么快速排序很好?

QuickSort takes N^2 in worst case and NlogN average case. The worst case occurs when data is sorted. This can be mitigated by random shuffle before sorting is started. QuickSort doesn't takes extra memory that is taken by merge sort. If the dataset is large and there are identical items, complexity of Quicksort reduces by using 3 way partition. More the no of identical items better the sort. If all items are identical, it sorts in linear time. [This is default implementation in most libraries]

快速排序总是比归并排序好吗?

不是真的。

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

注意:在java中，Arrays.sort()函数对基本数据类型使用快速排序，对对象数据类型使用归并排序。因为对象消耗内存开销，所以为归并排序增加一点开销对于性能来说可能不是什么问题。

参考:在Coursera上观看普林斯顿算法课程第三周的快速排序视频