基本思想：将外部数据分成若干份，分别移动到内存进行排序后输出。再归并排序。
链接1：http://blog.csdn.net/jeason29/article/details/50474772
优化：
- 增设一个缓冲buffer，加速从文件到内存的转储
- 流水线，并行实现，会引发资源冲突，因此将内存分为三份
- 最好不要用快速排序，因为速度不稳定，会影响流水线的效率
- 归并时候的优化：在内存中用堆表示读取进来的数，复杂度由O(n)降为O(logn)
链接2：http://blog.csdn.net/jxq0816/article/details/52487669
访问外存次数的计算：
一个含有2000个记录的文件，每个磁盘可容纳250个记录，则该文件包含8个磁盘块。然后对该文件作二路归并排序，每次往内存读入两个磁盘块，排序后再写回磁盘。把内存工作区等分为3个缓冲区。其中的两个为输入缓冲区。一个为输出缓冲区，在内存中利用简单二路归并merge函数实现二路归并。
每一趟对全部文件的处理需要8进8出，即读写16次。
其后有三趟归并(log2 8=3)。
故上述二路归并排序的总时间为：4*16=64。
增大归并路m，或减少初始归并段个数r，都能降低读写次数。
网友评论