题4

题4

题目

Q:设在磁盘上存放有 375000 个记录, 做 5 路平衡归并排序, 内存工作区能容纳 600 个记录, 为把所有记录排好序, 需要做 ( ) 趟归并排序.
A. 3 B. 4 C. 5 D. 6

分析

A:这和多路归并排序的公式是差不多的，那个是，这个公式是针对划分后的初始段而言的，段也就是m，也就是375000/600=625个初始段，5路归并，也就是每个段划分为5个子任务，也就是625/5=125个段，然后继续划分，直到划分为1个段，也就是需要4趟。

解

B
初始归并段的个数 ,因此,归并趟数 。
第一趟把 625 个归并段归并成 个;
第二趟把 125 个归并段归并成 个;
第三趟把 25 个归并段归并成 个;
第四趟把 5 个归并段归并成 个。