外部排序

概念与意义

• 当待排序的数据量太大，无法依次装入内存时，需要借助外部存储器（如硬盘）来完成的排序算法。这是大数据处理中的核心技术之一。

核心思想

• 外部排序使用分治策略
  • 分割阶段：将大文件分成若干个小的有序子文件
  • 合并阶段：将这些有序的归并段合并成一个完整的有序文件

基本算法流程

第一阶段：生成初始归并带

• 读取能装入内存的一块数据
• 在内存中堆这块数据进行排序（使用快速排序等内部排序算法）
• 将排序后恶数据写入临时文件作为一个归并段
• 重复上述步骤直到处理完所有数据

第二阶段：多路归并

• 同时打开多个归并段文件
• 从每个文件中读取一部分数据到内存缓冲区
• 使用多路归并算法合并这些数据
• 将合并结果写入输出文件
• 重复直到所有数据合并完成

关键参数分析

• N：总记录数
• M：内存能容纳的记录数
• B：磁盘块大小
• 初始归并段数量：$\lceil N/M \rceil$
• 归并路数：通常选择 $k = M/B - 1$（预留一个缓冲区给输出）

性能分析

时间复杂度

• 总的I/O次数：$O(N \times log_k[K/m])$
• 比较次数：$O(N \times log_k[N/M])$

空间复杂度

• 内存使用：$O(M)$
• 临时磁盘空间：$O(N)$

优化策略

• 替换选择排序：生成初始归并段时可以产生长度大于内存容量的归并段
• 多项归并：当归并段数量不是k的倍数时，使用多相归并可以减少归并趟数
• 缓冲区优化：为每个输入和输出文件分配合适大小的缓冲区；使用双缓冲技术overlap I/O和CPU计算