了解一下什么是外部排序算法

以前我们学习的排序算法，比如冒泡排序、插入排序、快速排序等都是属于内部排序，即所有排序操作都是在内存中完成。然而如果需要排序的文件比整个内存还大时，这时就无法将文件一次性放到内存中，需要借助外部存储来进行排序，这就是外部排序。

外部排序有两个步骤，分别是分与合：

• 分：首先将大文件分成n个小文件，每个小文件的大小需要小于内存的大小。然后依次将这些小文件放到内存中调用内排进行排序，处理完毕后会得到n个有序的小文件。

• 合：有了n个有序的小文件，怎么合并成1个有序的大文件呢？我们可以进行归并排序。

  举个例子，我们有三个小文件，内存的大小为3：
  文件1：3， 6， 9
  文件2：2， 4， 8
  文件3：1， 5， 7

  首先比较每个文件中的最小值，得出最小值后写入大文件。第一步比较3、2、1，拿出了最小值1写入大文件，第二步比较3、2、5，拿出了最小值2写入大文件，第三步比较3、4、5，拿出了最小值3写入大文件......循环执行这个步骤，最后即可完成排序。

上面的这个步骤其实就是3路平衡归并。因此，对于实际的场景中，对于 k-路平衡归并中的 k 值得选择，增加 k 可以减少归并的次数，从而减少外存读写的次数。但 k 的值也不是越大越好，k越大，在内存中选择最小值的时候也会更加花费时间。一般情况下，对于具有 m 个初始归并段进行 k-路平衡归并时，归并的次数为。

从公式中可以看出，要想提高算法效率，可以从两个角度实现：

• 一是增加 k-路平衡归并中的 k 值。
• 二是尽量减少初始归并段的数量m，增加每个归并段的容量。

但其实这两个角度是有矛盾之处的，实际场景中需要就综合考虑，平衡这两者了。