请求实现面向两个记录文件的Two way merge sort（C++版）

刚好对两路归并排序有不少实践经验，这就给你拆解清楚面向双记录文件的实现步骤——整个算法核心分为排序阶段和归并阶段两部分，细节如下：

排序阶段 #

这一步是为后续归并准备好有序的基础单元：

• 拆分待排序文件：把待排序的所有记录划分成若干个小组，每个小组叫做一个run，核心要求是单个run的大小必须能完全装进主内存，这样才能高效处理。
• 内部排序每个run：对每个单独的run使用适合内存数据的排序算法（比如快速排序、堆排序都行），把每个run变成有序的记录序列。
• 分配到两个外部文件：把所有排好序的run交替分配到两个独立的外部文件（比如叫File X和File Y）里，尽量让两个文件里的run数量差不多，方便后续归并操作。

归并阶段 #

这一步是把小的有序run逐步合并成完整的有序文件：

• 初始合并：从刚才生成的两个外部文件里各取一个有序run，用两路归并算法把它们合并成一个更大的有序run。
• 循环合并：不断重复上述合并操作，直到其中一个外部文件里的run被全部取完，这时候直接把另一个文件里剩下的所有有序run追加到结果里就行。
• 迭代归并（如果需要）：如果第一次合并后得到的run数量还是很多，就把这些新的有序run再次分配回两个外部文件，重复两两合并的过程，直到最终得到一个包含所有记录的完整有序文件。

小提示 #

归并过程中要注意内存的使用策略，每次只把两个待合并run的部分数据读入内存进行比较，减少磁盘IO的次数——毕竟外部文件的IO开销远大于内存操作，这是提升整个算法效率的关键。

内容的提问来源于stack exchange，提问作者Jack armour