归并排序变化

Question

要求通过合并排序4个阵列A，B，C和D的这些技术中的任何一个被允许：

1. 应用4路合并。
2. 合并A和B.将C与前一个合并的输出合并。最后将D与最后一个输出合并。
3. 将A与B和C合并为D.现在合并两个输出。

在比较和转移方面，每种技术的优点和缺点是什么？

Answer 1

有两种效率方法可以在这里考虑：

a。内存使用情况。

湾性能。

第一种技术具有低内存使用率，因为它不产生中间数组。

第三种技术具有很高的性能，因为A/B和C/D可以并行合并，然后合并中间数组。

最后，第二种技术既没有上述特征。