ai-infra-interview-305

第 282 题：大文件的external sort实现？k-way merge？

题目

大文件的external sort实现？k-way merge？

---

完整讲解

一、外部排序目的

数据量超过内存，无法一次性排序，需分块读入、排序、再合并。核心：利用磁盘顺序 IO，多路归并降低轮数。

二、流程与 k-way merge

阶段一：按内存能容纳的大小（如 M 条记录）读入、内排（快排等）、写出为有序段（run），得到多个有序文件。阶段二：k-way merge：同时打开 k 个有序段，用最小堆维护当前 k 个候选最小元；每次取堆顶输出，并从对应段补入下一条，直到所有段读完。k 越大，归并轮数越少，但需要 k 路缓冲与堆大小。

三、实现要点

内排阶段可并行（多块同时排序）。k-way 时堆中元素需带「来自哪一段」信息；段读完则从堆中移除该路。磁盘 IO 顺序读顺序写，性能好。可扩展为多轮 k-way（若段数远大于 k）。

---

面试要点

• 外部排序：分块读入、内排、写出有序段；再 k 路归并。
• k-way merge：用最小堆维护 k 个当前最小值；取堆顶输出并从对应段补入。
• 内排可并行；k 大可减少轮数但占缓冲；顺序 IO 友好。
• 堆中需记录元素来自哪一段，段读完则撤掉该路。

---

记忆要点

1. 两阶段：内排成多段 → k-way 归并。
2. k-way：最小堆 + 每路一个当前值；取堆顶、补该路下一条。
3. k 大则轮数少；顺序 IO；可多轮 k-way。

返回模块

返回总览