内排序的归并排序是采用二路归并。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序
外排序我们可以将这个“二”扩大到M。
将一个大文件分成M个小文件，每个小文件是有序的，然后对应在内存中我们开M个优先队列，每个队列从对应编号的文件中读取TopN条记录，然后我们从M路队列中各取一个数字进入中转站队列，并将该数字打上队列编号标记，当从中转站出来的最小数字就是我们最后要排序的数字之一，因为该数字打上了队列编号，所以方便我们通知对应的编号队列继续出数字进入中转站队列，可以看出中转站一直保存了M个记录，当中转站中的所有数字都出队完毕，则外排序结束。这考验的是我们的架构能力。
问题描述：
输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。
采取方法：1、归并排序，内存不够。2、位图法。3、多路归并
1、归并排序，内部排序。
2、位图法
例如：用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，边框用如下字符串来表示集合{1,2,3,5,8,13}：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0，上述集合中各数对应的位置则置1，没有对应的数的位置则置0。
针对我们的10^7个数据量的磁盘文件排序问题，我们可以这么考虑，由于每个7位十进制整数表示一个小于1000万的整数。我们可以使用一个具有1000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。采取这个位图的方案是因为我们面对的这个问题的特殊性：1、输入数据限制在相对较小的范围内，2、数据没有重复，3、其中的每条记录都是单一的整数，没有任何其它与之关联的数据。
三步进行解决：
第一步，将所有的位都置为0，从而将集合初始化为空。
第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。
第三步，检验每一位，如果该位为1，就输出对应的整数。
注意：
用此位图方法，严格说来还是不太行，空间消耗10^7/8还是大于1M（1M=1024*1024空间，小于10^7/8）。
既然如果用位图方案的话，我们需要约1.25MB（若每条记录是8位的正整数的话，则10000000/(1024*1024*8) ~= 1.2M）的空间，而现在只有1MB的可用存储空间，那么究竟该作何处理呢?
3、多路归并
假设文件中整数个数为N(N是亿级的)，整数之间用空格分开。首先分多次从该文件中读取M（十万级）个整数，每次将M个整数在内存中使用快速排序之后存入临时文件，然后使用多路归并将各个临时文件中的数据再次整体排好序后存入输出文件。
排序过程两部分构成：
1）内存排序
由于要求的可用内存为1MB，那么每次可以在内存中对250K的数据进行排序，然后将有序的数写入硬盘。
那么10M的数据需要循环40次，最终产生40个有序的文件。
2）归并排序
将每个文件最开始的数读入(由于有序，所以为该文件最小数)，存放在一个大小为40的first_data数组中；
选择first_data数组中最小的数min_data，及其对应的文件索引index；
将first_data数组中最小的数写入文件result，然后更新数组first_data(根据index读取该文件下一个数代替min_data)；
判断是否所有数据都读取完毕，否则返回2。
所以，本程序按顺序分两步，第一步、Memory Sort，第二步、Merge Sort。程序的流程图，如下图所示（感谢F的绘制）。
小结：
bit-map
适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下
基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码
扩展：bloom filter可以看做是对bit-map的扩展
问题实例：
1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。
2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-m
[外排序适用范围]
大数据的排序，去重基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树扩展。
问题实例：
1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。
具体实例详解：
链接 ：http://www.jianshu.com/p/1683cf5cc0c9
胜者树，败者树
胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。
同的是，胜者树的中间结点记录的是胜者的标号；而败者树的中间结点记录的败者的标号。
胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。在k路归并排序中经常用到。
区别：
在用胜者树的时候，每个新元素上升时，首先需要获得父节点，然后再获得兄弟节点，然后再比较。
在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。
所以总的来说，减少了访存的时间。
胜者树和败者树在每输出和补充一个值之后都要自底向上调整，每上升一层都需要一次比较，败者树是和父节点的一次比较，胜者树是和兄弟的一次比较，在比较的内存访问次数上二者没有太大的差别(或者胜者树可能好一点)。不同的是胜者树每次必然需要更新胜者(因为这条路径就是以原来的最终胜者为外部节点的路径，而原来的最终胜者已经被输出了)，但败者树每次不一定需要更新，这就代表它在每次上升时可能会少一次向内存的写入，因此更优
由于新加入的节点一定是替换了上一轮的胜者，那么对于胜者堆，从新节点到根之间路径节点存的都是上一轮的胜者，这些数据事实上对于本轮比较来说是无用的，但每次还要与兄弟节点比较去更新它。
而败者堆中，对于新更新的节点，它的父节点都是兄弟子堆的胜者，是最有价值、值得比较的数据，每次更新也都可以直接用于下轮比较。
http://blog.csdn.net/v_JULY_v/article/details/6451990 （赞）
http://blog.csdn.net/v_JULY_v/article/details/6279498 （超赞）
http://www.cnblogs.com/charlesblc/p/6138908.html
http://blog.csdn.net/msdnwolaile/article/details/52084983
http://blog.csdn.net/u013322907/article/details/38125641
http://blog.csdn.net/msdnwolaile/article/details/52084983
http://blog.csdn.net/v_JULY_v
http://blog.csdn.net/whz_zb/article/details/7425152
https://www.zhihu.com/question/35144290
