我们怎样才能进行8个元素的合并排序,只进行16次比较？

Question

好吧,几天前我问了一个关于排序的问题.我发现如何通过排序8个元素来证明最少的比较数是16,我理解为什么.但我的合并排序算法计算了17个比较,在我的情况下它是正确的.要合并两个长度为x和y的排序数组,我们需要(x + y)-1比较,因此在合并排序中我们得到17个比较.但它必须有16次比较,所以..怎么样？我在哪里可以保存1比较).

这是一张图片:

http://oeis.org/A001768

谢谢!

Answer 1

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

最低数量的比较不会使此算法成为最快的算法.例如,具有19个比较的Batcher奇偶合并输出容易胜过合并插入,因为它并行执行大多数比较.