100亿个数字的大文件如何快速找出最小的值？

又到了一年一度的面试季，最近有网友给出一道高级java工程师的面试题。100亿个数字的大文件如何快速找出最小的值？我这里给出一些思路，提供参考！

这道题我们首先想到的是使用外部排序的方式，由于内存的原因，内部排序肯定不被允许，或者不是最佳选择！

外部排序

内存极少的情况下，利用分治策略，利用外存保存中间结果，再用多路归并来排序。

map-reduce的嫡系

分割大文件

内存中维护一个极小的核心缓冲区memBuffer，将大文件bigdata按行读入，搜集到memBuffer满或者大文件读完时，对memBuffer中的数据调用内排进行排序，排序后将有序结果写入磁盘文件bigdata.xxx.part.sorted.
循环利用memBuffer直到大文件处理完毕，得到n个有序的磁盘文件：

合并多个排序结果

现在有了n个有序的小文件，怎么合并成1个有序的大文件？
把所有小文件读入内存，然后内排？
利用如下原理进行归并排序：

我们举个简单的例子：

文件1：3,6,9
文件2：2,4,8
文件3：1,5,7

第一回合：
文件1的最小值：3 , 排在文件1的第1行
文件2的最小值：2，排在文件2的第1行
文件3的最小值：1，排在文件3的第1行
那么，这3个文件中的最小值是：min(1,2,3) = 1
也就是说，最终大文件的当前最小值，是文件1、2、3的当前最小值的最小值，绕么？
上面拿出了最小值1，写入大文件.

第二回合：
文件1的最小值：3 , 排在文件1的第1行
文件2的最小值：2，排在文件2的第1行
文件3的最小值：5，排在文件3的第2行
那么，这3个文件中的最小值是：min(5,2,3) = 2
将2写入大文件.

也就是说，最小值属于哪个文件，那么就从哪个文件当中取下一行数据.（因为小文件内部有序，下一行数据代表了它当前的最小值）

最终的排序结果

less bigdata.sorted.text
...
9999966
9999967
9999968
9999969
9999970
9999971
9999972
9999973
9999974
9999975
9999976
9999977
9999978
...

： » 100亿个数字的大文件如何快速找出最小的值？