海量数据内存放不下时如何排序？外部排序的流程是什么？

简化版

海量数据排序通常用外部排序：先按内存大小把大文件切成多个块，每块读入内存后用快排/归并/库排序排好，写成有序小文件；再用多路归并把这些有序文件合成最终有序文件。归并阶段用小顶堆维护每一路当前最小元素，时间约 O(N log K)，K 是归并路数，核心瓶颈是磁盘 I/O。

详细版

当数据量大于内存，比如 500GB 日志、内存只有 4GB，不能一次性把所有记录读入数组排序。外部排序把问题拆成两步：第一步“生成有序 run”，每次读入一块能放进内存的数据，内部排序后落盘；第二步“多路归并”，每个 run 打开一个读缓冲区，用小顶堆取当前最小记录，写入输出缓冲区。

原始大文件
  -> 分块读入内存
  -> 每块内部排序
  -> run1, run2, run3, ...
  -> K 路归并
  -> 最终有序文件

若 run 数太多，不能同时打开太多文件或堆太大，就分多轮归并，例如每次 32 路合并，生成更大的中间 run，再继续合并。面试回答要强调：外部排序优化重点不是比较次数，而是顺序读写、缓冲区大小、归并路数、临时文件数量和磁盘 I/O 次数。

完整版教学

一、为什么内存排序方案会失效

普通排序默认所有数据都能放进内存，数组随机访问便宜，比较和交换是主要成本。海量排序里这个前提被破坏了：500GB 文件无法放进 4GB 内存，强行加载会 OOM；即便勉强分页，随机访问磁盘也会非常慢。因此外部排序首先要把“内存里的比较问题”改写成“磁盘上的顺序读写问题”。

举个数字例子：数据 100GB，内存可给排序使用 1GB，每条记录约 100B，那么总记录约 10 亿条，每块可装约 1000 万条，至少生成约 100 个有序块。此时排序的关键不是某个块内快排比归并快多少，而是如何把 100 个有序块高效合并。

场景	数据是否进内存	主瓶颈	常用方案
普通数组排序	是	CPU 比较和缓存	快排、归并、堆排、库排序
链表排序	是	指针重连	归并排序
海量文件排序	否	磁盘 I/O	外部排序，多路归并

二、第一阶段：生成有序 run

外部排序第一阶段叫 run generation。流程很直接：按内存上限读取一块数据，解析记录，使用内存排序算法排好，再写出一个临时有序文件。每个临时文件称为一个 run。只要每个 run 内部有序，后续就可以用归并把它们合起来。

块大小不能随便拍脑袋。块太小会生成大量 run，归并轮数变多；块太大又可能挤占系统内存，导致 GC 或页面置换。工程上通常预留输入缓冲、输出缓冲、堆、对象开销和系统余量，而不是把全部内存都给排序数组。

while 原始文件还有数据:
    records = 读取一个内存能容纳的块
    sort(records)
    写出 sorted-run-i.tmp

三、第二阶段：K 路归并怎么做

归并阶段的输入是多个已经有序的 run。每个 run 只需要维护一个当前候选元素，放入小顶堆；每次弹出堆顶，也就是所有 run 当前元素里的最小值，写到输出文件；然后从该元素所属 run 再读下一个元素入堆。这样不需要把所有 run 全部加载进内存。

假设有 4 个 run，当前首元素分别是 3、8、1、5，小顶堆先弹出 1；若 1 来自 run3，就从 run3 继续读下一个元素，比如 6，再入堆。整个过程每条记录入堆、出堆一次，堆大小是 K，所以 CPU 复杂度约 O(N log K)。

class Node {
    int value;
    int runId;
}

PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.value - b.value);
// 初始化：每个 run 读一个元素入堆
while (!pq.isEmpty()) {
    Node cur = pq.poll();
    write(cur.value);
    if (hasNext(cur.runId)) {
        pq.offer(readNext(cur.runId));
    }
}

记忆钩子：外部排序不是把大文件“排序一次”，而是先造很多小有序段，再像拉拉链一样把每一路的最小值不断拉出来。

四、归并路数 K 怎么选

K 越大，单轮能合并的 run 越多，归并轮数越少；但 K 太大时，每一路都要缓冲区和文件句柄，堆操作也更贵。真实系统还会受操作系统最大打开文件数、磁盘吞吐、记录解析成本影响。所以 K 的选择是 I/O 轮数和内存资源之间的平衡。

例如 100 个 run，如果一次 10 路归并，需要两轮：100 个合成 10 个，再合成 1 个。如果一次 50 路归并，也需要两轮，但每轮打开文件更多、缓冲区更碎。若能一次 100 路归并，则只需一轮，但必须确认文件句柄和缓冲区足够。

K 路归并	轮数倾向	内存/句柄压力	适合情况
K 小	轮数多	压力小	内存紧、文件句柄限制严
K 中等	平衡	可控	常见工程选择
K 很大	轮数少	压力大	内存足、句柄足、顺序 I/O 强

五、I/O 为什么比算法常数更重要

外部排序的核心成本是读写磁盘。第一阶段要读原文件、写 run；归并阶段每轮要读所有 run、写新 run。若归并多一轮，就可能多出一次全量读写。对 100GB 数据，多一轮就是额外约 200GB I/O，这通常比比较器里省几个 CPU 指令更关键。

因此优化重点是顺序读写、批量缓冲、减少临时文件轮数、避免频繁 seek。SSD 随机读写比 HDD 好很多，但顺序 I/O 仍然更稳定。分布式环境下还要考虑网络 shuffle、数据倾斜和失败重试，这时外部排序思想会演化成 MapReduce/Spark 的 sort shuffle。

两轮归并 I/O 粗略估算：
阶段1：读 100GB + 写 100GB
归并1：读 100GB + 写 100GB
归并2：读 100GB + 写 100GB
合计约 600GB 顺序 I/O

六、稳定性、去重和自定义记录怎么处理

外部排序经常排序的是记录，不只是整数。比较键可能是时间戳、用户 ID、分数，也可能是多字段组合。若要求稳定性，需要在比较键相同的时候保留原始顺序，可以附加全局序号作为次级 key，或确保 run 内排序和归并阶段都使用稳定规则。

如果目标是排序后去重，可以在归并输出时顺便处理：因为相同 key 会相邻，只要记住上一个输出 key，遇到重复就跳过或聚合。这个能力是外部排序在日志处理、倒排索引构建、离线 ETL 中常见的价值：一次顺序归并同时完成排序、去重、分组统计。

需求	做法	注意点
按多字段排序	比较器依次比较 key1、key2	字段解析要高效
稳定排序	相等时比较原始序号	序号会增加记录大小
排序后去重	归并输出时跳过相同 key	只适合同 key 相邻后的去重
分组聚合	归并时累积同 key	输出前处理最后一组

七、常见误区与追问

误区：外部排序就是把快排换成归并排序。 真正变化是数据不能全进内存，算法目标从随机访问比较变成分块排序和顺序归并。
误区：K 路归并 K 越大越好。 K 大会消耗文件句柄、缓冲区和堆比较成本，超过资源上限反而变慢或失败。
误区：复杂度只写 O(N log N) 就够。 外部排序必须讨论 I/O 轮数、顺序读写和临时文件规模，否则没有回答海量场景的核心。
追问：为什么归并适合外部排序？ 因为每个 run 都是顺序读取，输出也是顺序写入，对磁盘友好，不需要随机访问全量数据。
追问：如何处理内存只有 1GB、文件 100GB？ 先生成约百个 1GB 以内的有序 run，再按可承受的 K 做一轮或多轮 K 路归并。
追问：排序后要去重能否顺便做？ 可以，归并输出时相同 key 会连续出现，记录上一个 key 即可跳过或聚合。

八、加强记忆

海量排序的主线是“分块排序 + 多路归并”。第一阶段把大文件切成内存能吃下的小块，排成一个个有序 run；第二阶段用小顶堆维护每个 run 的当前元素，反复弹最小并补充同一路下一个元素。回答时要把瓶颈从 CPU 比较转到磁盘 I/O：顺序读写、归并路数、缓冲区、临时文件轮数，才是外部排序真正的面试考点。

简化版

详细版