面试的时候，有遇到这样一个问题：给你一个文件，每一行是一个IP段，IP段之间互不交叉。以后会给你很多IP，让你判断在不在这些IP段中，如果在则返回对应IP段。
文件格式可能如下:
125.25.59.1, 125.25.129.42
200.24.1.35, 250.142.0.0
我回答把IP地址转化为一个数值，然后做排序，建立一个二叉搜索树，每来一个IP地址做二分查找。面试官说IP段不会有变动了，我说那不用树直接用一个数组就可以。
面试官又说，如果内存当中不能一次处理所有数据呢？我不假思索的说，要用外部排序。
外部排序merge小文件的时候应该是用K路归并+败者树，我当时竟然说二路归并！
位图法
回来之后，我发现应该有更好的办法，比如“位图法”，位图法排序适用于数据不重复，并且数据分布在一个有限的集合里。
如果数据没有重复，那么就可以用位图来表示，每一个bit代表一个数，0代表这个数没出现过，1代表出现过。首先扫描一遍数据，构造好位图来表示，然后再扫描一遍位图，将标志为1的数（出现过的数）按序输出。
其伪代码为：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//磁盘文件排序位图方案的伪代码
//copyright@ Jon Bentley
//July、updated，2011.05.29。
//第一步，将所有的位都初始化为0
for i ={0,....n}
bit[i]=0;
//第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。
for each i in the input file
bit[i]=1;
//第三步，检验每一位，如果该位为1，就输出对应的整数。
for i={0...n}
if bit[i]==1
write i on the output file
对于上文这个问题来说，因为IP段是互不交叉的，所以可以用位图法来做。IP地址一共有 256^4 个，约为4*10^9。如果在位图中每一个只需一个bit来标志，只需0.5G内存就可以了。但是给出的是IP段，我们可以按照IP段的起始IP排序，不过必须记录IP段的终止IP，每一个IP得到的数值正好用4个字节可以保存。但是仔细算算，这就需要16G，就算扫描两次，每次记录一半的位图，一次至少也得需要8G，如果扫描两次以上的次数，就比外部排序更慢了。
如果内存比较小，对于IP段这种特殊情况，位图法排序好像不大行的通。
外部排序
别人的博客讲了一种 “选择置换+败者树”的方法。
1.如果内存大小限制n, 采用选择置换获得的小的有序顺串的大小是大于n的。
2.采用败者树的方法，每次获得一个当前最小值只需要比较logK次，而普通K路归并需要比较K-1次。
（感觉也可以用最小堆，时间复杂度是O(MlogK)，空间复杂度是O(K)，和败者树一样）。