外部排序

外部排序是一种处理大量数据的排序方法，尤其是当数据太大而不能完全装入内存时。这种排序方法通常使用分治策略，将大问题分解为小问题，对小问题进行解决，然后再将解决方案组合成大问题的解决方案。

以下是外部排序的基本步骤，其中最典型的方法是多路归并排序：

1. 分阶段 (Split Phase)：
   • 数据被分割成多个小文件。每个小文件的大小基本上与可用内存相匹配。
   • 读取一个小文件大小的数据到内存中，使用传统的排序算法（如快速排序、堆排序等）对数据进行排序。
   • 将排序后的数据写回到磁盘。
2. 归并阶段 (Merge Phase)：
   • 采用多路归并算法，从每个小文件中读取一部分数据到内存。
   • 将这些数据进行合并，并将结果写回到一个新的输出文件中。
   • 当所有小文件都被完全读取并归并后，输出文件就是完全排序好的数据。