Merge 算法将两个排序的输入数组合并为一个排序的输出数组，方法是重复比较两个输入数组的最小元素，并将两个数组中较小的元素移至输出。
现在我们需要将三个相同长度的已排序输入数组(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(记录 n 次)
对于 O(kn lg n) 的数组写入净数。另一方面，如果您在每一步都使用 k 路比较，那么您将执行 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 路合并会为总共 O(nk lg k) 次内存操作执行 O(nk) 次写入和 O(nk lg k) 次比较。迭代双向合并算法对总共 O(nk lg n) 次内存操作执行 O(nk lg n) 次写入和 O(nk lg n) 次比较。因此，对于一些长序列，k 路归并渐近更好，而对于许多短序列，迭代归并排序更快。
希望这对您有所帮助!
关于algorithm - Mergesort 对三个输入数组进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2367545/