多路归并通过最小堆管理K路有序序列的当前最小值，实现边读边选、边合并边输出，时间复杂度O(n log K)，空间复杂度O(K)，适用于海量外部数据流式处理。

多路归并不是把所有数据一次性读进内存再排序，而是利用“各路已有序”这一前提，边读边选、边合并边输出，特别适合处理无法全量加载的海量外部变量序列（如分块排序后的小文件、日志流、数据库分片结果等）。

核心思路：用最小堆管理每路当前最小值

面对 K 个外部有序序列（比如 K 个已排序的文件或数组），关键在于避免每次扫描全部 K 个首元素——那样时间开销是 O(nK)。改用最小堆（优先队列），只维护 K 个“当前待比较元素”，每次取最小值仅需 O(log K)，整体复杂度降至 O(n log K)。

• 每个堆节点存三元组：（值，来源序列编号，该序列内索引）
• 初始化：把每路第一个有效元素入堆（跳过空序列）
• 循环：弹出堆顶 → 输出 → 若该路还有下一元素，则将它推入堆
• 结束条件：堆为空，即所有序列均已耗尽

Java 实战要点：适配外部存储结构

真实场景中，“序列”往往来自文件、数据库游标或网络流，不能直接用 int[] 操作。需封装为统一接口：

• 定义 SequenceReader 接口：含 hasNext() 和 next() 方法，屏蔽底层差异
• 初始化堆时，对每个 reader 调用一次 next() 获取首值；若抛出异常或返回 null，跳过该路
• 合并过程中，reader 只在需要时才触发下一次 I/O，实现真正的流式处理
• 注意资源释放：每路 reader 在遍历完后应 close()，可用 try-with-resources 或显式管理

空间与稳定性控制技巧

外部归并常受限于内存，需精细控制缓冲区和中间状态：

• 堆大小严格为 ≤ K，不随总数据量增长 —— 这是 O(1) 空间增量的关键
• 输出不缓存全量结果，而是逐个写入目标文件或流，避免内存溢出
• 相等元素的相对顺序由入堆顺序隐式保持（Java PriorityQueue 稳定性需自定义 Comparator 处理 tie-break）
• 若某路数据极大（如单个文件超 10GB），可配合预读缓冲区（如 BufferedInputStream）提升 I/O 效率

典型外部场景示例：大日志文件归并

假设你有 8 个按时间戳升序排列的日志文件（access_0.log ~ access_7.log），每文件含百万行。目标是合并为一个全局时间有序的 access_all.log：

• 为每个文件创建 FileLineReader，按行解析时间戳转 long 值作为 key
• 堆中初始存 8 个 (timestamp, fileIndex, lineNum)，按 timestamp 小根排序
• 每次 pop 后，从对应文件读下一行，解析新 timestamp 入堆；若 EOF，则不再入堆
• 输出时直接 write 到新文件，全程内存占用仅约 8×（一行文本 + 元信息）