应聘的一个题目，外排序
前几天参加一个公司的招聘，笔试题的最后一道题目是：
A文件中最多有n个正整数，而且每个数均小于n，n <=10的七次方。不会出现重复的数。
要求对A文件中的数进行排序，可用内存为1M，磁盘可用空间足够。
我考虑的是把这个文件的记录分割成x个小块的文件（足够小到1M的内存可以处理）然后调入内存使用快速排序对这x个小文件里面的记录排序，最后再把这些小的文件归并。
后来面试的时候hr问能不能够在10秒时间内搞定，我以前没有做过这样的外排序，只能说不知道。
请问各位大虾，这个问题能够在10s内搞定吗？如果可以，是应该怎么做的？
[解决办法]
用位图，
10s内排序搞定应该没有问题。
1M内存有点少， （1M = 8M bits), 可以代表8M整数，现在n <=10的七次方， 你可以读2遍文件，就可以完成排序了。第一次排n <8M得数， 第2遍排 8M <n <10的七次方的数。
[解决办法]
Programming Pearls 编程珠玑 第二版
网上有中文扫描的PDF
内容稍微有点杂，但还是值得一看的。
[解决办法]
归并需要大约16次，每次都要对硬盘进行305次的硬盘读操作和305次的硬盘写操作，目前的硬盘的响应时间是以0.01毫秒级来计算的，故不考虑快速排序花的时间，也要花费近10秒的时间用于对硬盘的读写（Dell Inspirson6000类型的机子），因此在10秒内是不能做到的。
