外部排序通常采用归并排序的方法 首先根据缓冲区的大小将外存上含有n个记录的文件分成若干长度为h的子文件，依次读入内存并利用有限的内部排序算法对它们进行排序，并将排序后得到的有序子文件重新写回外存，通常称这些有序子文件为归并段或顺串 然后对这些归并段进...

失败树：树形选择排序的一种变体，可视为一棵完全二叉树 每个叶结点存放各归并段在归并过程中当前参加比较的记录，内部结点用来记忆左右子树中的‘失败者’，胜利者向上继续进行比较，直到根结点

置换-选择排序：

m路归并排序可用一棵m叉树描述 归并树：用来描述m归并，并只有度为0和度为m的结点的严格m叉树 带权路径长度之和为归并过程中的总读记录数： 用哈夫曼树构造的叫最佳归并树：