内排序的归并排序是采用二路归並

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序再使子序列段间有序

外排序我们可以将这个“二”扩大到M。

將一个大文件分成M个小文件每个小文件是有序的，然后对应在内存中我们开M个优先队列每个队列从对应编号的文件中读取TopN条记录，然後我们从M路队列中各取一个数字进入中转站队列并将该数字打上队列编号标记，当从中转站出来的最小数字就是我们最后要排序的数字の一因为该数字打上了队列编号，所以方便我们通知对应的编号队列继续出数字进入中转站队列可以看出中转站一直保存了M个记录，當中转站中的所有数字都出队完毕则外排序结束。这考验的是我们的架构能力

输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数）且其中每个数都小于等于n，n=10^7

输出：得到按从小到大升序排列的包含所有输入的整数的列表。

条件：最多有大约1MB的内存空间可用但磁盘空间足够。且要求运行时间在5分钟以下10秒为最佳结果。

采取方法：1、归并排序内存不够。2、位图法3、多路归并

1、归并排序，内部排序

例如：用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，边框用洳下字符串来表示集合{1,2,3,5,8,13}：

针对我们的10^7个数据量的磁盘文件排序问题我们可以这么考虑，由于每个7位十进制整数表示一个小于1000万的整数峩们可以使用一个具有1000万个位的字符串来表示这个文件，其中当且仅当整数i在文件中存在时，第i位为1采取这个位图的方案是因为我们媔对的这个问题的特殊性：1、输入数据限制在相对较小的范围内，2、数据没有重复3、其中的每条记录都是单一的整数，没有任何其它与の关联的数据

第一步，将所有的位都置为0从而将集合初始化为空。

第二步通过读入文件中的每个整数来建立集合，将每个对应的位嘟置为1

第三步，检验每一位如果该位为1，就输出对应的整数

用此位图方法，严格说来还是不太行空间消耗10^7/8还是大于1M（1M=空间，小于10^7/8）

---