1. 定义

　　排序是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。

　　内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。【衡量内排序的效率是数据的比较次数】

　　外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。【衡量外排序的效率是内存与外存的交换次数】　

　　内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

2. 分类

　　稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，归属于不稳定排序。(稳定：插冒归基；不稳定：快选堆希)

　　就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1），则称为就地排序。

　　精简排序：对一对数字不进行两次和两次以上的比较。（精简：直接插入，归并排序）

1. 实现外部排序的两个过程：

2. 时间组成：

3. 为了提高整个外部排序的效率，分别从以上两个方面对外部排序进行了优化：

在实现将初始文件分为 m 个初始归并段时，为了尽量减小 m 的值，采用置换-选择排序算法(内部使用败者树实现)，可实现将整个初始文件分为数量较少的长度不等的初始归并段。
同时在将初始归并段归并为有序完整文件的过程中，为了尽量减少读写外存的次数，采用构建最佳归并树的方式（哈夫曼树实现），对初始归并段进行归并（败者树实现），而归并的具体实现方法是采用败者树的方式。

4. 优化递进顺序：

5 胜者树 & 败者树 & 堆排序

发展历史

- 堆：其实一开始就是只有堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。
- 胜者树：这时人们想能否简化比较过程，这时就有了胜者树，这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。而胜者树在节点上升的时候首选需要获得父节点，然后再获得兄弟节点，然后再比较。
- 败者树：这时人们又想能否再次减少比较次数，于是就有了败者树。在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。
- 所以总的来说，减少了访存的时间。现在程序的主要瓶颈在于访存了，计算倒几乎可以忽略不计了。

相同点

首先它们三个的相同点就是在于：空间和时间复杂度都是一样的O(N*log^N)。调整一次的时间复杂度都是O(log^N)的。
所以这道题用堆来做，跟用败者树来做并没有本质上的算法复杂度量级上的差别。

不同点

堆：所有的节点都是关键字；每次调整一层需要比较两次（父亲左孩子| 父亲右孩子）。
胜者树：叶子节点是关键字，非叶子节点保存胜者索引；每次调整一层需要比较1次（自己兄弟），读取两次（父亲| 兄弟）。
败者树：叶子节点是关键字，非叶子节点保存败者索引；每次调整一层需要比较1次（自己父亲），读取一次（父亲），只需要和路径上的节点比较，不需要和兄弟节点比较，简化了重构的过程。；新增B[0]记录比赛的胜者【在本例子中是ls[0]】