置换-选择排序能生成更长初始归并段，因其动态维护MINIMAX门槛，边读边选边输出：新记录≥刚输出值即加入当前段，否则暂存为下一段起点；相同内存下平均段长达2l，显著减少归并趟数。
置换-选择排序为什么能生成更长的初始归并段
因为它不等内存填满再输出，而是边读、边选、边输出——只要新读入的记录 ≥ 刚刚输出的记录，就允许它“插队”进当前归并段。传统内部排序（如 std::sort）必须把整批数据装入内存才能开始排，结果每个归并段长度被硬限制为内存容量 l；而置换-选择在相同内存下，平均能产出长度约 2l 的归并段，直接减少归并趟数。
核心逻辑：MINIMAX 记录怎么选
关键不是找全局最小，而是找“不小于上一个输出值”的最小值。每次输出后，新读入的记录只有满足 new_key >= last_output_key 才参与下一轮选择；否则暂存，留作下一归并段起点。这个动态门槛机制是延长段长的根本原因。
- 初始化时读入
l个记录，建败者树（或最小堆），选出最小值作为首个MINIMAX - 输出该值后，从外存读一个新记录：若
new_key >= MINIMAX，插入败者树并参与下次选择；否则标记为“待用”，不入树 - 重复上述过程，直到败者树中所有剩余记录都 MINIMAX → 当前归并段结束
- 把所有“待用”记录重新装入内存，开始下一归并段
败者树比堆更适合这个场景
因为每次只替换一个叶子节点（刚输出位置），且只需向上调整一条路径，时间复杂度稳定在 O(log l)；而堆在替换后需 heapify 整棵子树，最坏 O(l)。更重要的是，败者树天然支持“屏蔽某些节点不参与比较”——那些 last_output_key 的待用记录，可以直接从比较路径中跳过，无需移除或重建结构。
实际编码中，如果不用败者树而用 std::priority_queue，就得额外维护一个待用队列，并在每次选 MINIMAX 前手动过滤掉不满足条件的元素，容易漏判或重复插入。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
常见错误：边界处理导致段长骤降
最典型的是忽略“最后一轮读入可能为空”或“待用记录未清空就开启新段”。比如内存容量 l = 6，但某次归并段结束时只用了 5 个待用记录，第 6 个位置为空——若代码仍尝试读入第 6 个，就会触发文件末尾错误或默认值污染；又或者把上一段残留的待用记录混进新段，破坏单调性。
- 每次读外存前，先检查
if (file.eof() || file.fail())，避免无效读入 - 待用记录应存于独立容器（如
std::vector<Record>），归并段结束时清空，新段开始前才批量装入 -
MINIMAX初始值设为极小值（如INT_MIN），首轮不校验大小关系，否则第一个记录永远无法入选 - 输出阶段若发现败者树为空且无新记录可读，必须强制终止当前段，哪怕它很短
真正难的不是算法骨架，而是外存 IO 与内存状态的精确同步——少一次 read() 或多一次 push()，整个归并段的单调性就崩了。
