使用 k 路合并的外部排序与快速排序
哪一个更好？ 假设 1GB 内存和 100GB 文件要排序。
10路合并需求的一个实例： - 100 1GB 负载，然后是 10*10 + 10*100 100MB 负载（对于 10 路合并，然后是 10 路合并）
Quicksort 需要 100*7*2 (nlogn) 1GB 负载？
Which one is better?
Say 1GB memory and 100GB file to sort.
One instance of 10-way merging needs:
- 100 1GB loads followed by 10*10 + 10*100 100MB loads (for 10-way followed by 10-way merging)
Quicksort needs 100*7*2 (nlogn) 1GB loads?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
处理大数据时，归并排序的 IO 效率更高。
原因是因为快速排序是一种自上而下的方法，
这意味着您必须先处理 100GB，然后再处理 50GB * 2 ...
当数据量很大时，不可能将整个数据放入内存中。
换句话说，合并排序是一种自下而上的方法，正如您所描述的，您可以分离数据
分成适合内存的小批量，并将它们合并到缓冲区中。
Merge sort is more IO efficient when processing large data.
The reason is because quick sort is a Top-bottom approach,
which means you have to process the 100GB first, and than process 50GB * 2 ...
it is impossible to fit whole data into memory when you have large data.
in other way, merge sort is a bottom-up approach , as you described, you can separate data
into small batch which can fit into memory, and merge them in buffer.
主要瓶颈实际上是硬盘驱动器的读取和写入。我们从硬盘驱动器中读取每个元素两次，并从硬盘驱动器中写入每个元素两次。每次对块进行排序，然后再次进行多路合并。
相比之下，快速排序平均将每个元素读/写到硬盘驱动器 O(log n) 次。
The main bottleneck will actually be reading from and writing to the hard drive. We read each element from the hard drive twice and write each element from the hard drive twice. Once each for sorting the chunks and then once each again for the multi-way merge.
In contrast, quicksort will read/write each element to the harddrive on average O(log n) times.