为什么quicksort比mergesort更好？
我在接受采访时被问到了这个问题。 他们都是O（nlogn），但大多数人使用Quicksort而不是Mergesort。 这是为什么？
Quicksort具有O（n2）最差情况运行时和O（nlogn）平均情况运行时。 然而，在许多情况下，它优于合并排序，因为许多因素会影响算法的运行时间，并且当它们一起使用时，快速排序会胜出。
特别是，经常引用的排序算法的运行时间指的是执行排序数据所需的比较次数或交换次数。 这确实是衡量性能的一个好方法，尤其是因为它独立于底层硬件设计。 然而，其他的东西 - 比如参考的地点（也就是说，我们读了很多可能在缓存中的元素吗？） - 在当前的硬件上也扮演着重要的角色。 特别是Quicksort需要很少的额外空间并且具有良好的缓存局部性，这使得它在许多情况下比合并排序更快。
此外，通过使用适当选择的关键点（例如随机选取它）（这是一个出色的策略），很容易避免快速排序的最差情况O（n2）的运行时间。
在实践中，许多现代的quicksort实现（特别是libstdc ++的std::sort ）实际上是introsort，其理论最坏情况是O（nlogn），与合并排序相同。 它通过限制递归深度来实现这一点，并且一旦超过logn就切换到不同的算法（heapsort）。
正如许多人所指出的，快速排序的平均情况下性能比mergesort快。 但是，如果您假设按需访问任意一块内存的时间不变，那才是真实的。
在RAM中，这个假设通常不会太差（因为高速缓存它并不总是如此，但它并不算太坏）。 但是，如果你的数据结构足够大，可以存放在磁盘上，那么快速排序会被平均磁盘每秒执行200次随机查找的事实所杀死。 但是，同一张磁盘没有任何问题顺序读取或写入每秒兆字节数据。 这正是mergesort所做的。
因此，如果数据必须在磁盘上进行排序，那么确实需要在mergesort上使用一些变化。 （通常你快速排列子列表，然后开始将它们合并到一定大小的阈值以上。）
此外，如果您必须对这种大小的数据集进行任何操作，请认真思考如何避免查找磁盘。 例如，这就是为什么标准建议您在数据库中执行大量数据加载之前先删除索引，然后再重建索引。 在加载过程中保持索引意味着不断寻找磁盘。 相比之下，如果删除索引，那么数据库可以通过首先对要处理的信息进行排序（当然使用合并），然后将其加载到索引的BTREE数据结构中来重建索引。 （BTREE自然保持顺序，所以你可以从一个排序数据集中加载一个，只需要很少的搜索到磁盘。）
在很多情况下，理解如何避免磁盘搜索让我能够使数据处理工作花费数小时而不是几天或几周的时间。
实际上，QuickSort是O（n2）。 它的平均运行时间是O（nlog（n）），但是最坏的情况是O（n2），当您在包含少量独特项目的列表上运行时，会发生这种情况。 随机化需要O（n）。 当然，这并没有改变最坏的情况，它只是防止恶意用户使你的排序花费很长时间。
QuickSort更受欢迎，因为它：