外部排序是数据量超内存时的唯一可行方案，采用分而治之：先分块内排生成有序段，再用最小堆多路归并，时间复杂度o(n log k)，空间复杂度o(k)。
当数据量远超内存容量，无法一次性载入排序时，外部排序是唯一可行方案。核心思路是分而治之：先将大数据切分为多个能装入内存的块，各自内部排序后写回磁盘；再通过多路归并，逐步合并这些有序块，最终得到全局有序结果。
分块排序（生成有序段）
将输入文件按内存上限划分为若干子文件（runs）。例如，若可用内存为100MB，每条记录占1KB，则一次可加载约10万条记录。逐批读入、快排（或堆排）、写入临时文件（如 run_0.dat、run_1.dat），确保每个文件内部有序。注意使用缓冲I/O减少磁盘开销，并避免频繁创建小文件——可适当增大单次处理规模以平衡内存与IO效率。
多路归并（合并有序段）
归并阶段不追求一次性读完所有run，而是用最小堆管理各run的当前首元素：
- 初始化：从每个run读取第一条记录，构建大小为k（run总数）的最小堆
- 重复弹出堆顶（当前最小值），写入输出文件；再从对应run读入下一条记录，插入堆中
- 某run读完后，不再补充，堆大小自然减小
该方法时间复杂度为 O(N log k)，其中N为总记录数，k为分块数；空间复杂度稳定在 O(k)，仅需存储k个指针+少量缓冲区。
优化策略与常见陷阱
实际应用中需关注几个关键点：
- 块大小自适应：不要固定按内存上限切分。若数据存在局部有序性（如时间序列日志），可启用“顺串识别”，延长初始run长度，减少归并轮数
- 磁盘IO调度：归并时多个run并发读取易引发磁盘寻道抖动。建议顺序读取run（配合预读缓冲），或使用SSD降低随机IO代价
- 内存映射替代手动读写：对大文件，mmap可简化实现并利用系统页缓存，但需注意脏页刷盘时机和跨平台兼容性
- 避免中间文件爆炸：多级归并时，勿将每轮结果全写磁盘。可采用“败者树”或双缓冲机制，在内存中暂存部分归并结果，减少落盘次数
工具与工程建议
不必从零实现。Linux sort命令默认支持外部排序：sort -S 512M -T /tmp bigfile.txt > sorted.txt，自动完成分块与归并。若需嵌入代码，Python的heapq.merge()适合已打开的有序文件迭代器；Java可借助PriorityQueue + BufferedReader组合。重点始终是：控制单次内存占用、减少磁盘随机访问、让归并逻辑清晰可测。
