快速排序是一种就地排序算法，因此它更适合于数组。另一方面，归并排序需要额外的O(N)存储空间，更适合于链表。

与数组不同，在喜欢列表中，我们可以在中间插入O(1)空间和O(1)时间的项，因此归并排序中的归并操作可以在不需要任何额外空间的情况下实现。但是，为数组分配和取消分配额外空间会对归并排序的运行时间产生不利影响。归并排序也有利于链表，因为数据是按顺序访问的，没有太多的随机内存访问。

另一方面，快速排序需要大量的随机内存访问，而使用数组，我们可以直接访问内存，而不需要像链表那样进行任何遍历。同样，快速排序用于数组时具有良好的引用局部性，因为数组连续存储在内存中。

尽管这两种排序算法的平均复杂度都是O(NlogN)，但通常人们在执行普通任务时使用数组进行存储，因此快速排序应该是首选算法。

编辑:我刚刚发现归并排序最差/最好/平均情况总是nlogn，但快速排序可以从n2(最坏的情况下，元素已经排序)到nlogn(平均/最佳情况下，pivot总是将数组分为两半)。

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.

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

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

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

维基百科的解释是:

通常，快速排序在实践中比其他Θ(nlogn)算法要快得多，因为它的内部循环可以在大多数架构上有效地实现，并且在大多数现实数据中，可以做出设计选择，使需要二次时间的概率最小化。

快速排序

Mergesort

我认为归并排序(即Ω(n))所需要的存储量也存在快速排序实现所不具备的问题。在最坏的情况下，它们的算法时间是相同的，但归并排序需要更多的存储空间。

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

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

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

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

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

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

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

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