外部排序，多路归并

题目

• 写一个函数，输入是很多个文件，每个文件中是很多float的数值，文件内部无序。输出是一个有序的大文件，内存约束2个G，具体怎么实现比较高效？

思路

• 大文件分小文件(分治)->每个小文件内部排序（可以用堆）->得到k个有序的小文件后，多路归并
• 多路归并方法：
  • 方法一：暴力
    • 选择每个有序小文件的第一位，组成一个长度为k的数组，再排序（堆），取最小值写入大数组；然后在取出数对应的小文件中再取出一个数放入数组继续
  • 方法二：败者树
    • 构建k个叶子节点的数，每对叶子节点的父节点存这对叶子节点中最小值（如果你设置的是想要最大值的话；或者最大值，看你设置的规定）的索引，然后胜者跟下一对叶子节点的胜者对比。败者树求得最小值的复杂度为O(logN)；采用败者树而不采用胜者数的原因是败者树在维护的时候更方便，因为败者树的重构只需要与其父结点比较。

参考

• 海量数据多路归并排序的c++实现（归并时利用了败者树）
• 胜者树与败者树