external-sorting - 外部排序与 k 路合并与快速排序

Question

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

10 路合并的一个实例需要： - 100 个 1GB 加载，然后是 10*10 + 10*100 个 100MB 加载（对于 10 路，然后是 10 路合并）

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

Answer 1

在处理大数据时，合并排序的 IO 效率更高。

原因是因为快速排序是一种自上而下的方法，这意味着您必须先处理 100GB，然后再处理 50GB * 2 ...当您有大数据时，不可能将整个数据放入内存中。

换句话说，合并排序是一种自下而上的方法，正如您所描述的，您可以将数据分成可以放入内存的小批量，然后将它们合并到缓冲区中。

Answer 2

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

相比之下，快速排序将平均 O(log n) 次将每个元素读/写到硬盘驱动器。