阶段一:生成初始归并段
将数据按内存大小分成若干块,每块内部排序
读: 0
写: 0
阶段二:k路归并
将各归并段进行多路归并
?
外部排序说明外部排序用于处理无法一次性装入内存的大规模数据。分为两个阶段:
1. 生成初始归并段:将文件分成若干段,每段读入内存进行内部排序,再写回外存。
2. 多路归并:使用k路归并将多个有序归并段合并成一个完整的有序文件。
时间复杂度 O(n log n) 主要开销:磁盘I/O