在归并排序中，一般算法为:

对左子数组进行排序 对右子数组进行排序 合并两个已排序的子数组

在顶层，合并两个已排序的子数组涉及处理N个元素。

再往下一层，第3步的每次迭代都涉及处理N/2个元素，但您必须重复此过程两次。所以你仍然在处理2 * N/2 == N个元素。

再往下一层，你要合并4 * N/4 == N个元素，以此类推。递归堆栈中的每个深度都涉及合并相同数量的元素，涉及对该深度的所有调用。

考虑一下快速排序算法:

选择一个枢轴点 将枢轴点放置在数组中的正确位置，所有较小的元素放在左边，较大的元素放在右边 对左子数组进行排序 对右子数组排序

在顶层，你处理的是一个大小为n的数组，然后选择一个枢轴点，把它放在正确的位置，然后可以在算法的其余部分完全忽略它。

再往下一层，您将处理2个子数组，它们的组合大小为N-1(即减去之前的枢轴点)。为每个子数组选择一个枢轴点，总共有2个额外的枢轴点。

再往下一层，您将处理4个子数组，它们的组合大小为N-3，原因与上面相同。

然后N-7…然后c15…然后N-32…

递归堆栈的深度保持大致相同(logN)。使用归并排序，你总是在递归堆栈的每一层处理n个元素的归并。但是使用快速排序，你要处理的元素数量会随着你在堆栈中向下移动而减少。例如，如果你在递归堆栈中查看深度，你正在处理的元素数量是N - 2^((logN)/2)) == N -根号(N)。

声明:对于归并排序，因为每次都将数组分割为两个完全相等的块，所以递归深度正好是logN。在快速排序时，由于枢轴点不太可能恰好位于数组的中间，因此递归堆栈的深度可能略大于logN。我还没有做过数学计算，看看这个因素和上面描述的因素在算法复杂性中究竟扮演了多大的角色。

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

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

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

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

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

正如其他人所注意到的，快速排序的最坏情况是O(n²)，而归并排序和堆排序则停留在O(nlogn)。然而，在平均情况下，这三个都是O(nlogn);所以它们在大多数情况下是可比较的。

平均而言，快速排序更好的地方在于，内循环意味着将多个值与单个值进行比较，而在其他两个循环中，每次比较时两个项都是不同的。换句话说，Quicksort的读取次数是其他两种算法的一半。在现代cpu上，访问时间在很大程度上决定了性能，因此快速排序最终成为一个很好的首选。

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

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

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

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

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

亩! 快速排序并不比归并排序更好，它非常适合于不同类型的应用。

归并排序是值得考虑的，如果速度是本质，糟糕的最差情况性能不能容忍，并且有额外的空间可用

你说他们«他们都是O(nlogn)[…]»。这是错误的。«快速排序使用大约n^2/2比较在最坏的情况下。

然而，根据我的经验，最重要的属性是在使用带有命令式范式的编程语言进行排序时，可以轻松实现顺序访问。

1 Sedgewick，算法

One of the reason is more philosophical. Quicksort is Top->Down philosophy. With n elements to sort, there are n! possibilities. With 2 partitions of m & n-m which are mutually exclusive, the number of possibilities go down in several orders of magnitude. m! * (n-m)! is smaller by several orders than n! alone. imagine 5! vs 3! *2!. 5! has 10 times more possibilities than 2 partitions of 2 & 3 each . and extrapolate to 1 million factorial vs 900K!*100K! vs. So instead of worrying about establishing any order within a range or a partition,just establish order at a broader level in partitions and reduce the possibilities within a partition. Any order established earlier within a range will be disturbed later if the partitions themselves are not mutually exclusive.

任何自下而上的排序方法，如归并排序或堆排序，就像工人或雇员的方法一样，人们很早就开始在微观层面进行比较。但是，一旦在它们之间发现了一个元素，这个顺序就必然会丢失。这些方法非常稳定和可预测，但要做一定量的额外工作。

Quick Sort is like Managerial approach where one is not initially concerned about any order , only about meeting a broad criterion with No regard for order. Then the partitions are narrowed until you get a sorted set. The real challenge in Quicksort is in finding a partition or criterion in the dark when you know nothing about the elements to sort. That is why we either need to spend some effort to find a median value or pick 1 at random or some arbitrary "Managerial" approach . To find a perfect median can take significant amount of effort and leads to a stupid bottom up approach again. So Quicksort says just a pick a random pivot and hope that it will be somewhere in the middle or do some work to find median of 3 , 5 or something more to find a better median but do not plan to be perfect & don't waste any time in initially ordering. That seems to do well if you are lucky or sometimes degrades to n^2 when you don't get a median but just take a chance. Any way data is random. right. So I agree more with the top ->down logical approach of quicksort & it turns out that the chance it takes about pivot selection & comparisons that it saves earlier seems to work better more times than any meticulous & thorough stable bottom ->up approach like merge sort. But