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

Question

一种合并算法通过反复比较两个输入数组的最小元素，并将两个输入数组中较小的一个移动到输出中，将两个排序输入数组合并成一个排序输出数组。

现在，我们需要将三个长度相同的排序输入数组(A1、A2和A3)合并到一个(排序)输出数组中，并且有两种方法：

array.

• Revising

• 采用上述合并算法将A1和A2合并为A4，然后使用相同的算法将A4和A3合并为输出A4算法，通过反复比较三个输入数组的最小元素，并将最小的一个移动到输出数组。

如果只考虑最坏的数组元素移动(即赋值)，那么上述两种算法中哪一种更有效？

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

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

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 n)。另一方面，如果您在每一步都使用k路比较，那么就可以精确地执行kn写操作，这要小得多。

现在，让我们考虑一下您在每个设置中做了多少比较。在三向合并中，写入输出序列的每个元素都需要找到三个值的最小值。这需要两个比较--一个比较前两个序列的第一个值，另一个比较这两个值的最小值与第三个数组的第一个值。因此，对于写入结果序列的每个值，我们使用两个比较，而且由于编写了3n个值，所以最多需要进行6n比较。

要做到这一点，一个更好的方法是将序列存储在一个min堆中，在这个堆中，序列通过它们的第一个元素进行比较。在每一步中，我们用最小的第一个值将序列从堆中排出，将该值写入结果，然后将序列的其余部分排队回堆中。对于k序列，这意味着写出的每个元素最多需要O(lg )比较，因为堆插入在O(lg )中运行。这给出了O(kn )的净运行时，因为写出的每个kn元素都需要O(lg )处理时间。

在另一个版本中，我们首先做一个标准的双向合并，它要求每个元素进行一个比较，以获得2n个比较的净总和。在合并的第二次传递中，在最坏的情况下，我们总共进行了3n比较，因为有3G元素正在合并。这给出了5n个比较的净总数。如果我们使用上面描述的用于成对合并的广义构造，我们将需要使用O(kn lg n)比较，因为编写的每个元素都需要一个比较，而O(kn lg n)写。

简而言之，对于k=3的具体情况，我们有三路合并进行3n写入和对9n内存进行读写网络的6n比较。迭代的双向合并进行5n写入和5n比较，为10n内存的净读写，因此三向合并版本更好。

如果我们考虑广义结构，k-路合并做O(nk)写入和O(nk lg k)比较，总共O(nk lg k)内存操作。迭代的双向合并算法对总共O(nk lg n)内存操作进行O(nk lg n)写入和O(nk lg n)比较。因此，k-way合并对于一些长序列来说是渐近性更好的，而迭代合并排序对于许多短序列则更快。

希望这能有所帮助！