Q3-数据结构

题目

(摘自王道考研数据结构8.7.6习题第六题)

做m路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置几个输入缓冲区和输出缓冲区？

分析

课本中给的例子都是单独进行的，就是说每一轮的内部归并排序和输入输出的读写是同时发生的，所以说针对四路归并排序，课本中给出来的示意图如下所示。

但是本题说的是要求并行执行，所以说如果说是一个m路归并的话，需要设计2m个输入缓冲区，2个输出缓冲区。

答：2m个输入缓冲区 和 2个输出缓冲区

理由：

1.增加一个输出缓冲区，当一个输出缓冲区满时，通知通道进行输出，同时归并程序向第二个输出缓冲区填充数据，这就实现了内部归并和输出的并行

2.增加m个输入缓冲区，当m个缓冲区正在运行时，外部可以向正在工作的m个缓冲区对应的第二个缓冲区（也就是增加的m个缓冲区）写入数据，这就实现了输入和内部归并的并行

综上两点，增加1个输出和m个输入缓冲区，即设置 2个输出 2m个输入缓冲区 即可实现输入/内部归并/输出的并行处理。

参考

1. 做m路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置几个输入缓冲区和输出缓冲区？ - LEON的回答 - 知乎 ↩