8.7.2 外部排序的方法
原书定位
印刷页P387起,对应PDF第399页。下文为目视整理的知识提要;完整内容见原书对照。
路归并通常需 个输入缓冲区和至少 1 个输出缓冲区。每个输入段当前块用完再读下一块,输出缓冲满则写回;各段均耗尽后结束该组归并。
个初始段平衡做 路归并,所需趟数约 。若文件占 块,每趟全量读写为 次,含初始段形成的简化总 I/O 为 ;题目不写回最终结果或有缓存时应按实际修正。
增加 可减少趟数,但会占更多缓冲,也增加每次选最小段首的工作。提高初始段长度可减少 ,同样可能减少归并趟数。

二路外部归并的缓冲区与归并树,原书P388。

四路外部归并过程,原书P388。
对应练习
关联知识
原书对照
展开原书对照截图

