外排序是处理无法全部装入内存中的大数据量排序问题时采用的一种排序方法。它的核心思想是分阶段处理，主要包括两个相对独立的阶段：产生初始归并段和多路归并排序。初始归并段的生成是通过置换-选择排序算法来完成的，该算法的核心在于不断地将内存中的数据替换掉最大关键字的记录，通过败者树选取最小记录的方式，将剩余的记录依次组织成初始归并段。在多路归并排序阶段，需要将初始归并段按照某种规则合并，以达到最终的排序目的。
置换-选择排序算法的具体步骤是从内存工作区的记录开始，通过比较和替换来决定哪些记录可以构成初始归并段。在上述示例中，给定的关键字序列T=(12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18)，内存工作区可以容纳4个记录，通过置换-选择排序算法得到的初始归并段为归并段1和归并段2。
多路平衡归并是将多个初始归并段按照k路平衡归并树的原则进行合并的过程。其目的是减少归并的总趟数，提高效率。多路平衡归并的关键在于每个结点的子树高度相差不超过1，这样的归并树可以保证归并过程中尽可能地减少数据的移动次数。
败者树是一种数据结构，它用于在k路归并过程中选择关键字最小的记录。败者树实际上是一棵完全二叉树，用于在记录中比较选出最小关键字的记录。败者树的每一个叶子结点代表一个记录，内部节点用于记录比较过程中失败的记录，即关键字较大者。最终，树的根节点会指向最小关键字的记录。
在外排序的具体操作中，例如一个文件经过内排序得到了80个初始归并段，那么问题就在于如何用最少的归并趟数完成排序。这里需要根据多路平衡归并的公式来计算，找到可以满足条件的最小归并路数。如果归并路数为k，则趟数s的计算方式是log以k为底m的对数。例如，如果要完成排序的初始归并段有80个，用多路平衡归并方式需要3趟完成，则至少应取的归并路数为5。
另外，操作系统可能对同时可用的输入/输出文件的总数有限制，比如限制为不超过15个。在这种情况下，如何选择合适的路数和趟数，就需要计算得到一个最优的归并策略。具体到本例，如果要限定在2趟内完成排序，那么最低路数至少为9，即执行9路排序。
置换选择排序算法在实际应用中，还可能得到不同长度的初始归并段。如示例中提到的8个初始归并段，它们的记录个数分别为37、34、300、41、70、120、35和43。对于这些不同的段，排序时还需要进一步考虑如何最优地合并这些归并段。
外排序的主要知识点包括置换-选择排序算法、多路平衡归并、败者树、归并路数的确定以及归并趟数的计算。这些知识点是进行大规模数据排序时不可或缺的理论基础。在实际应用中，要综合考虑硬件条件和排序算法的特点，设计出既高效又实用的外排序策略。
