外存模型-- 外存排序问题(理论)

归并排序的基本思想

外存排序本质上是一种归并排序，比如说 我们将数组一分为二，然后这两段每一段都是有序的，然后我们把这两段进行合并，这个就是归并排序的思想。

外存排序

但是外存排序并不能一分为二，原因是内存的大小是有限的，内存和外存的交互是以磁盘块为基本单位的，如下图所示，每次内存装满的情况下 可以容纳M/B个磁盘块。放到内存排序以后再往外写。

执行过程：

1. 首先将M的数据放入内存并排序,然后直接写入外存
2. 之后将排号序的数据取每个M的第一块放入内存，这里先放入15 47 23 留一块作为输出缓冲区
3. 重复2过程，那么得到的数据就是有序的。

IO 复杂度分析

• 对于整个数据 扫描的次数是N/B
• 把内存装满的IO次数是M/B
• 首先所有的数据都需要放入内存中洗牌那么次数是N/B

进行的是M/B-1路归并 每次读写数据一次 就是N/B 一共的IO还取决于层数所以是N/B * LOG… 最后把M换成B的原因在下面。

1. 第一轮有序序列的最大长度是M/B
2. 第二轮有序序列的最大长度是(M/B-1)*M/B
3. 以此类推 每一次排序需要读写数据一次
   建立右边图片的等式 解出归并次数，那么就可以完成整个问题的求解，最后再对结果进行优化。