合并排序变量

Question

需要合并4个排序数组A, B, C和d。以下任何一种技术都是允许的:

1. 应用4路合并。
2. 合并A和b，将C与前一次合并的输出合并。最后将D与最后的输出合并。
3. 将A与B合并，C与d合并。

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

Answer 1

这里需要考虑两个效率指标:

。内存使用。

b。性能。

第一种技术占用内存很少，因为它不产生中间数组。

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

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