为什么Quicksort比mergesort更好？

Question

采访中有人问我这个问题。它们都是O（nlogn），但是大多数人使用Quicksort而不是Mergesort。这是为什么？

Answer 1

正如许多人所指出的，Quicksort的平均案例性能比mergesort更快。 但这只有在假设您有恒定的时间按需访问任何内存时才是正确的。

在RAM中，此假设通常不太差（由于高速缓存，它并不总是正确的，但也不太糟）。但是，如果您的数据结构足够大，可以存储在磁盘上，那么快速排序就会因您的平均磁盘每秒执行200次随机寻道而被杀死。但是，同一张磁盘没有顺序顺序读取或写入每秒兆字节数据的麻烦。mergesort正是这样做的。

因此，如果必须在磁盘上对数据进行排序，那么您真的很想在mergesort上使用一些变体。（通常，您先对子列表进行快速排序，然后在某个大小阈值以上开始将它们合并在一起。）

此外，如果您必须对如此大小的数据集执行任何操作，请认真考虑如何避免寻找磁盘。例如，这就是为什么这样的建议，即在数据库中进行大量数据加载之前先删除索引，然后再重建索引，这是标准建议。在加载期间保持索引意味着不断寻找磁盘。相反，如果删除索引，则数据库可以通过以下方式重建索引：首先对要处理的信息进行排序（当然使用mergesort！），然后将其加载到该索引的BTREE数据结构中。（BTREE本质上是保持顺序的，因此您可以从排序的数据集中加载一个，而很少有磁盘寻道。）

在很多情况下，了解如何避免磁盘寻道使我使数据处理作业花费数小时而不是数天或数周。

Answer 2

实际上，QuickSort是O（n ²）。它的平均运行时间为O（nlog（n）），但最差的运行时间为O（n ²），当您在包含很少的唯一项目的列表上运行它时，会发生这种情况。随机化为O（n）。当然，这不会改变最坏的情况，它只是防止恶意用户使您的排序花费很长时间。

QuickSort之所以受欢迎，是因为它：

1. 就地（MergeSort要求额外的内存与要排序的元素数量成线性关系）。

2. 有一个小的隐藏常数。