缘起
昨晚，小平问我如何对大文件进行分割。虽然目前她没有对大文件进行排序的需求，但我想以后很可能会用到。
我想了一个解决方法，是先将大文件分割为若干子文件，然后将各子文件分别加载在内存中进行排序，最后将各排好序的子文件合并为大文件。但是这种方法要求各子文件之间的大小已经确定。以升序为例，即对于子文件 f1, f2, ..., fn，要求 any(f1) <= any(f2) <= ... <= any(fn)，这样最好的简单合并才能确保所有记录的有序。
因此，我提出，在划分子文件前，要先遍历大文件一次，统计各数值出现的次数，然后按分布来确定几个分割的阈值，再遍历大文件各条记录，按阈值划分子文件。
以上我的解决方案是可行的，但是我想应该不是最优的，对于子文件的划分有些麻烦。我想看看别人是怎么解决大文件排序问题的，因此这个问题应该很典型了。然后我发现了外部排序，这是和内部排序相对的存在，我以前竟然不知道，看来还是对数据结构及算法学的不够系统。
外部排序 (External sorting)
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序。
归并排序 (Merge Sort)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用**分治法（Divide and Conquer）**的一个非常典型的应用。
首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
多路归并排序 (K-Way Merge Algorithm)
多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k。
- (1)假设有K路数据流，流内部是有序的，且流间同为升序或降序
- (2)首先读取每个流的第一个数，如果已经EOF，pass
- (3)将有效的k (k可能小于K)个数比较，选出最小的那路min-k，输出，读取min-k的下一个
- (4)直到所有K路都EOF
后记
大数据时代，大文件随处可见，而我们的计算机内存有限，必须借助外部存储来解决看似只能在内存中处理的问题。我们的大脑亦如此。我们每天接收的信息何止千千万，我们无法记住所有的信息，只能采撷精华，进行思考，而就是这些经过思维提炼后的精品也难保不会随着时间的流逝而逐渐忘却。因此，我们也需要借助我们大脑外的空间来存储我们无处安放或容易遗忘的知识和信息，以前是纸质笔记本，现在是电脑存储。正像罗辑思维里所说，机器现在已经成为我们的外延，未来不存粹是人类或机器人的争夺，而是人和机器的融合。