外排序核心思路是分块排序加归并合并：先将大文件按内存容量切分为多个小块，逐块载入内存排序后写回磁盘生成有序归并段；再通过k路归并（常用最小堆实现）多轮合并这些段，减少I/O次数，最终得到全局有序文件。
外排序核心思路：分块排序 + 归并合并
内存受限时无法一次性读入整个大文件，必须把文件切分成能装进内存的块，每块单独排序后写回磁盘，再用多路归并把已排序的块合并成最终有序文件。关键不是“怎么快”，而是“怎么不爆内存”和“怎么减少 I/O 次数”。
典型流程：split → sort-in-memory → write-chunk → merge-chunks。其中 merge-chunks 是最易出错的环节——不是简单两两合并，而是用最小堆做 k 路归并，否则时间复杂度会退化到 O(n²)。
用 std::priority_queue 实现 k 路归并时要注意什么
不能直接把整块数据 load 进内存再归并，每个 chunk 只需维护一个“当前游标”（即下一个待比对的元素）。std::priority_queue 存的是 {value, chunk_id, offset} 三元组，每次 pop 最小 value 后，从对应 chunk 读取下一个元素（如果还有）再 push 进堆。
- 堆比较函数必须严格弱序，避免
operator 对相等 value 未定义行为导致未定义结果 - 每个 chunk 文件需保持打开状态（
std::ifstream），但不要一次性seekg到末尾——按需读取，避免预读放大 I/O - 若 chunk 数量 k 很大（比如 >100），堆操作开销明显，可考虑分层归并（先 8 路合并为中间文件，再合并中间文件）
如何控制 chunk 大小与内存用量
chunk 大小不是越大越好。假设可用内存为 M 字节，你要留出约 20% 给归并阶段的缓冲区、堆结构和系统开销，剩余约 0.8M 用于单次加载和排序。若元素是 int（4 字节），则 chunk 最多容纳 0.8 * M / 4 个元素；若元素含字符串或自定义结构，必须按实际 sizeof 和对齐计算，别信“大概”。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
常见错误：std::vector::reserve 不等于 std::vector::resize，没初始化就访问会触发未定义行为；用 std::vector::emplace_back 逐个构造比 push_back 更省内存。
文件 I/O 的实际坑点：缓冲与编码
用 std::ifstream / std::ofstream 默认是带缓冲的，但若 chunk 文件超大（如 >1GB），建议显式调用 rdbuf()->pubsetbuf 设置更大缓冲区（如 64KB），否则小粒度 read/write 会让系统调用次数爆炸。
文本格式下尤其注意：\n 在 Windows 是 \r\n，若原始文件混用换行符，std::getline 可能读出带 \r 的脏数据，导致排序错乱。二进制模式读写更可控，但要求数据本身支持序列化（比如用 reinterpret_cast<char>(&x)</char> 写 int）。
真正难的不是算法逻辑，而是把每一块的生命周期管清楚：哪个文件句柄该关、哪段内存该释放、哪个临时文件该删——漏掉一个，跑三次就磁盘满。
