答案将略微倾向于快速排序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

但大多数人使用快速排序而不是归并排序。为什么呢?”

一个没有给出的心理学原因是，快速排序的名字更为巧妙。很好的市场营销。

是的，带有三重分区的快速排序可能是最好的通用排序算法之一，但“快速”排序听起来比“归并”排序强大得多，这是无法克服的事实。

快速排序有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)来实现这一点。

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

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

这是采访中经常被问到的一个问题，尽管归并排序在最坏情况下性能更好，但快速排序被认为比归并排序更好，特别是对于大输入。以下是快速排序更好的原因:

1-辅助空间:快速排序是一种就地排序算法。就地排序意味着执行排序不需要额外的存储空间。另一方面，归并排序需要一个临时数组来归并已排序的数组，因此它并不到位。

2-最坏情况:快速排序O(n^2)的最坏情况可以通过使用随机化快速排序来避免。通过选择正确的枢轴，可以很容易地避免这种情况。通过选择合适的枢轴元来获得平均情况下的行为，从而提高了算法的性能，达到了与归并排序一样的效率。

3-引用的局部性:快速排序特别展示了良好的缓存局部性，这使得它在许多情况下比归并排序更快，比如在虚拟内存环境中。

4-尾递归:快速排序是尾递归，而归并排序不是。尾递归函数是一种函数，其中递归调用是函数执行的最后一件事。尾递归函数被认为比非尾递归函数更好，因为尾递归可以被编译器优化。

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

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

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

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