Mergesort对三个输入数组进行排序

Question

合并算法通过重复比较两个输入数组中的最小元素，并将两个输入数组中的较小元素移至输出，将两个排序后的输入数组合并到排序后的输出数组中。

现在我们需要相同长度的3个排序输入阵列（A1，A2，和A3）合并为一个（排序）输出阵列，并且有两种方法：

1. 使用上述合并算法将A1和A2合并为A4，然后使用相同的算法将A4和A3合并到输出数组中。

2. 通过反复比较三个输入数组中最小的元素并将三个中最小的一个移动到输出数组，修正上述合并算法。

如果仅考虑数组元素运动（即赋值）的最坏情况，上述两种算法中的哪一种更有效？

如果仅考虑数组元素比较的最坏情况，上述两种算法中的哪一种更有效？

在这两种算法之间，哪一种算法在最坏情况下具有更高的整体效率？

Answer 1

如果您关心的只是阵列写入次数，第二个版本（三路合并）比第一个算法（双向合并的两个实例）快。三路合并算法将完成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路合并渐近地更好，而对于许多短序列，迭代合并排序更快。

希望这会有所帮助！