外部排序与k路合并与快速排序

Question

哪一个更好？ 说1GB内存和100GB文件进行排序。

的10路合并需要一个实例： - 100 1GB负载，随后用10个* 10 + 10 * 100 100MB负载（10路，随后用10路合并）

快速排序需要100 * 7 * 2（nlogn）1GB负载？

Answer 1

合并排序在处理大数据时更有效率。

的原因是因为快速排序是，这意味着你必须先处理100GB顶底的做法， ，比50GB的过程* 2 ... 就不可能适应整个数据到内存中，当你有大数据。

以其他方式，合并排序是一种自下而上的方法，正如您所描述的那样，您可以将数据 分成可以放入内存的小批量，并将它们合并到缓冲区中。

Answer 2

主要瓶颈实际上是读取和写入硬盘驱动器。我们从硬盘读取每个元素两次，并从硬盘写入两个元素。一次用于对块进行排序，然后每次再进行一次用于多路合并。

相比之下，快速排序将在平均O（log n）次时读/写每个元素到硬盘。