1.外部排序的基本概念
对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序
需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换
2.外部排序的方法
基本概念：文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的。外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数
外部排序通常采用归并排序法
归并排序优化：增大归并路数k，减少初始归并段个数r
3.多路平衡归并与败者树
引入败者树的背景：为了使内部归并不受k（归并路数）的增大的影响
基本思想：败者树是树形选择排序的一种变体，可视为一颗完全二叉树。k个叶结点分别存放k个归并段在归并过程中当前参加比较的记录，内部结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小树
4.置换-选择排序
