algorithm - 8个元素的归并排序只需要16次比较怎么办？

Question

嗯，我前几天问了一个关于排序的问题。我发现了如何通过对 8 个元素进行排序来证明最少的比较次数是 16，并且我明白了原因。但是我的合并排序算法计算了 17 次比较，在我的例子中它是正确的。要合并两个长度分别为 x 和 y 的已排序数组，我们需要 (x+y)-1 次比较，因此在合并排序中我们得到 17 次比较。但必须有 16 次比较，所以..如何？我在哪里可以保存那 1 个比较)。

这是一张图片:

http://oeis.org/A001768

谢谢!

Answer 1

OP 包含一个明确的证据，证明 8 个元素的合并排序 少于 17 次比较是不可能的。与其他算法相比，仍然可以在 16 次比较中对 8 个元素进行排序。该算法在 D.Knuth 的“计算机编程艺术”第 3 卷第 5.3.1 章中有所描述。它被命名为合并插入。

最少的比较次数并不能使该算法成为最快的算法。例如，Batcher odd–even mergesort进行 19 次比较很容易胜过合并插入，因为它并行执行大多数比较。