外部排序是408数据结构中让很多考生头疼的专题，尤其是I/O次数的计算，看似有公式可套，但实际做题时错误率很高。核鲸计算机考研从常见错误出发，梳理外部排序I/O计算的核心逻辑，帮助考生真正把这个考点做对。

一、外部排序I/O计算的基本框架

外部排序的I/O次数计算基于归并排序的多路归并模型。基本公式是：总I/O次数 = 初始归并段生成阶段的I/O次数 + 各趟归并过程的I/O次数。初始阶段每个记录读一次写一次，产生2n次I/O（n为记录总数）；每趟归并同样每个记录读一次写一次，也是2n次；总趟数由归并路数和初始归并段数量决定。理解这个框架，比死记公式更容易在变体题目中正确计算。

二、最常见的错误：趟数计算出错

大多数I/O计算错误出在趟数上。趟数的计算公式是：趟数 = ⌈log_k(m)⌉，其中k是归并路数，m是初始归并段数量。常见错误有三类：第一，把初始归并段的生成阶段当成"第0趟"纳入趟数计算，导致多算一趟；第二，k路归并中误把k和m的关系搞反；第三，在引入置换选择算法后初始归并段减少，忘记重新计算m的值就代入原来的公式。每一类错误都会导致最终结果差距较大。

三、置换选择算法对初始归并段的影响

使用置换选择算法生成初始归并段时，平均段长约为内存工作区大小的两倍，初始归并段数量减少，从而减少归并趟数。很多考生在做题时忽略题目是否使用了置换选择，直接用原始记录数除以内存块数得到初始段数，导致段数偏多、趟数偏多、最终I/O次数偏大。遇到题目中提到"置换选择"，要先重新计算初始归并段数，再代入趟数公式。

四、最优归并树与I/O最小化

最优归并树（哈夫曼树思想在外部排序中的应用）是另一个常见考查角度。当各初始归并段长度不等时，按照哈夫曼树的构造规则合并，可以使总I/O次数最小。考题通常给出若干初始归并段的长度，要求计算最优归并顺序下的最小I/O次数。这类题目的关键是正确建树并计算带权路径长度，之后乘以2（读+写）即为I/O次数。核鲸计算机考研覆盖外部排序的全部考查角度，帮助考生系统掌握这一高频失分点，稳定得分。