合并算法通过重复比较两个输入数组的最小元素并将两个输入数组中较小的一个移动到输出，将两个排序的输入数组合并为一个排序的输出数组。
现在我们需要将三个相同长度的排序后的输入数组（A1、A2、A3）合并成一个（排序后的）输出数组，有两种方法：
使用上述 Merge 算法将 A1 和 A2 合并到 A4 中，然后使用相同的算法将 A4 和 A3 合并到输出数组中。
修改上述 Merge 算法，通过反复比较三个输入数组的最小元素，并将三个中最小的一个移动到输出数组。
如果仅考虑数组元素移动（即分配）的最坏情况，上述两种算法中哪一种更有效？
如果只考虑数组元素比较的最坏情况，上述两种算法中哪一种更有效？
在这两种算法中，哪一种在最坏情况下具有更高的整体效率？
如果您只关心数组写入的数量，那么第二个版本（三向合并）比第一个算法（双向合并的两个实例）更快。三路合并算法将执行 3n 次写入（其中 n 是任何序列的长度），因为它一次合并所有三个范围。第一种方法会将两个范围合并在一起，执行 2n 次写入，然后将该序列与第三个序列合并，执行 3n 次写入，总共 5n 次写入。
更一般地，假设您有 k 个元素范围，长度均为 n。如果您成对合并这些范围，然后再次成对合并这些合并，等等，那么您将大致执行 k/2 个合并步骤，合并长度为 n 的范围，然后 k/4 合并长度为 2n 的范围，然后 k/8 个合并长度 4n 等。这给出了总和
kn/2 + kn/2 + ... + kn/2 (log n 次)
对于 O(kn lg n) 的净数组写入次数。另一方面，如果您在每一步都使用 k-way 比较，那么您确实会执行 kn 次写入，这要小得多。
现在，让我们考虑一下您在每个设置中进行了多少次比较。在三路合并中，写入输出序列的每个元素都需要找到三个值中的最小值。这需要两次比较 - 一次比较前两个序列的第一个值，一次比较这两个值的最小值与第三个数组的第一个值。因此，对于写入结果序列的每个值，我们使用两次比较，并且由于写入了 3n 个值，我们总共需要进行最多 6n 次比较。
一个更好的方法是将序列存储在一个最小堆中，其中序列通过它们的第一个元素进行比较。在每一步中，我们将具有最小第一个值的序列从堆中出列，将该值写入结果，然后将序列的其余部分排入堆中。对于 k 个序列，这意味着写出的每个元素最多需要 O(lg k) 次比较，因为堆插入在 O(lg k) 中运行。这给出了 O(kn lg k) 的净运行时间，因为写出的每个 kn 元素都需要 O(lg k) 处理时间。
在另一个版本中，我们首先进行标准的双向合并，这需要每个写入的元素进行一次比较，总共进行 2n 次比较。在合并的第二遍中，在最坏的情况下，我们总共进行了 3n 次比较，因为有 3G 元素被合并。这给出了总共 5n 次比较。如果我们使用上述的成对合并的广义构造，我们将需要使用 O(kn lg n) 比较，因为写入的每个元素都需要一个比较，而我们执行 O(kn lg n) 写入。
简而言之，对于 k=3 的特定情况，三路合并针对 9n 次内存读取和写入的网络执行 3n 次写入和 6n 次比较。迭代的双向合并执行 5n 次写入和 5n 次比较，总共净读取和写入 10n 次内存，因此三向合并版本更好。
如果我们考虑广义结构，k-way 合并执行 O(nk) 次写入和 O(nk lg k) 次比较，总共 O(nk lg k) 次内存操作。迭代的双向合并算法执行 O(nk lg n) 次写入和 O(nk lg n) 次比较，总共 O(nk lg n) 次内存操作。因此，k 路归并对于一些长序列渐近更好，而迭代归并排序对于许多短序列更快。
希望这可以帮助！