algorithm - 合并排序变体

Question

需要合并 4 个排序数组 A、B、C 和 D。允许使用以下任何一种技术：

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

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

Answer 1

这里有两个效率衡量标准：

一个。内存使用情况。

湾。表现。

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

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

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