实现硬盘排序-N路归并排序
简介： 排序分为内部排序和外部排序。在对较大规模数据进行排序时，由于内存容量的限制，往往无法将数据全部加载到内存中一次性排序。硬盘排序（外部排序）可以解决这个问题。我在科研工作中需要对海量的卷积神经网络浮点类型参数进行排序，于是自己手写了一个Java排序工具，该工具类采用N路归并排序算法。N路归并排序算法以及工具的参考源码将在本文中介绍。
关键词：外部排序；硬盘排序；多路归并排序；大数据；内存排序；
N路归并排序
算法中有一种分治思想，将一个大问题分而治之，各个突破，当子问题解决了，大问题也就KO了。内排序的归并排序是采用二路归并的，因为分治后有LogN层，每层两路归并需要N的时候，最后复杂度为NlogN，那么外排序我们可以将这个“二”扩大到M，也就是将一个大文件分成M个小文件，每个小文件是有序的，然后对应在内存中我们开M个优先队列，每个队列从对应编号的文件中读取TopN条记录，然后我们从M路队列中各取一个数字进入中转站队列，并将该数字打上队列编号标记，当从中转站出来的最小数字就是我们最后要排序的数字之一，因为该数字打上了队列编号，所以方便我们通知对应的编号队列继续出数字进入中转站队列，可以看出中转站一直保存了M个记录，当中转站中的所有数字都出队完毕，则外排序结束。
源码实现逻辑
将原始的大数据文本文件，先拆分成很多的小文件存放在磁盘中
对每个小文件进行一次性的内部排序，将有序的小文件再放回磁盘
由于每个小文件都是有序的，接下来我们只需要将这些小文件合并成一个大文件就行了。合并的方法是查看 每个小文件中的第一个数，取其中最小的数存入最终结果的大文件中。直至所有小文件的数据都被合并到大文件中。
最终得到的大文件就是有序的。