Lesson15：外部排序

情景：数据量太大，无法全部加载到内存中，希望实现与磁盘的外部交互。

磁盘未免太难， 我们这里使用的是"磁带"，假设其有一个读写头，仅能朝着一个方向上移动。

N代表数字的个数，M代表内存能handle的宽度。加1是因为划分block需要1次。

run就是排完序的block。

target: + 减少合并次数 + 加快run的合并 + 希望与内存的读写的速度加快 + run的产生过程更高效点

观察公式的直观想法：改变\(log_2\)的这个底数2，也就是每次多处理几个run。

从成本理解也好理解，磁盘比内存便宜吧。

解释一下这个过程，使用了一个最小堆的数据结构，你看不是三个元素的堆吗，比如第一次移入11\12\17，把11取出来再塞入81，以此类推，相当于每次经历一个deleteMin与insert过程。

直观演示：

e.g. 10个磁带，那么底数就是5，因为某一情景用到的磁带在另一情景不能使用，也就是n/2。

最慢的其实是拉读写头的过程(也就是所谓的pass)

e.g. 不均匀划分的例子，如34个runs但只有三个磁带

依次类推，最后就会变成一个。

然后就有个问题，我们发现能正好1/1->1runs的情况下，这个原来的数应该得是斐波那契数，如果不是咋办？

不是的话我们往更大的数上靠，增添一些INT_MAX之类的大数就可以了。

这里考虑的是多线程的优化方法。

以及generate a longer run，之前限制run是因为内存的长度限制，那我们可以这样设想：把我们的最小堆判断一下， 要是接下来这个元素比刚刚吐出来的元素小，那显然不能仅最小堆(不然无序了)，那如果更大我们就也把他放进最小堆排序，这样等效于是增大了run大小。

这一方法称为replacement selection

减小merge开销

本质就是huffman tree，挑小的来就行(找软柿子捏)。