（1）开篇
一、抽象问题
作者在被问到一个问题：“怎样给一个磁盘文件排序”时，起初想到的是一些有关如何在磁盘上实现归并排序的简单思想。而当深究问题的细节时会发现，通过磁盘上的归并排序不能是的问题被很好的解决。于是，对问题进行更客观、更易用的形式描述：
输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7。如果输入文件中有重复的数则出错。
输出：升序排列输入整数的列表，并重写入原文件中。
约束：最大有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间若能在10秒以内则不需要进一步优化。
二、程序设计
1、一种直观的利用磁盘归并排序的思想的解决方案是如果用32位整数来存储每个7位数字的话，1MB空间内科存储250000个号码。因此，可以使用遍历输入文件40次的程序来完成排序。第一次对0~249999之间的整数排序，第二次对250000到499999之间的数排序，以此类推，最后经过40次的文件读写，完成整个文件的排序。此方法有多次的文件的读写，运行时间会很长，不可取。
2、用位图或位向量表示集合。每个7位十进制的整数表示一个小于1000万的整数，我们使用一个具有1000万位的字符串来表示这个文件。若整数i存在于文件中，则第i位为1，否则为0。这种表示利用了一些属性：输入数据限制在相对较小的范围内；数据没有重复；对每条记录而言，除了单一整数外，没有任何其他相关数据。
可分三个阶段来编程，第一阶段将所有位初始化为0，第二阶段读入文件中的每个整数来建立集合，将每个对应的位都设置为1，第三阶段检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出文件。
三、原理
对小问题的仔细分析有时可得到明显的益处。该实例阐明了一下原理：
1、明确的问题；
2、位图数据结构，该数据结构描述了一个有限定义域内的稠密集合，其中每一个元素最多出现一次并且没有其他任何数据与该元素相关联；
3、多趟算法，多次读入数据，每次完成一步；
4、时间-空间的权衡；
5、简单的设计，简单的设计的标准不是不能再增加任何东西，而是不能再减少任何东西。
四、本章问题的一个位图算法实现
变量top初始为0，下面的代码实现对数组元素i的首次访问：
from[i] = top;
to[top] = i;
data[i] = 0;
top++;
