How can we carry out merge sort of 8 elements with only 16 comparisons?

Question

Well, I asked a question about sorting few days ago. I found out how to prove that the least number of comparisons by sorting 8 elements is 16 and I understood why. But my merge sort algorithm counts 17 comparisons and in my case it is right. To merge two sorted arrays with length x and y each we need (x+y)-1 comparisons, so in merge sort we get 17 comparisons. But it must be possible with 16 comparisons, so.. how? where can I save that 1 comparison).

Here is an image:

http://oeis.org/A001768

Thanks!

Answer 1

OP contains a clear proof that merge sort of 8 elements is not possible with less than 17 comparisons. Still it is possible to sort 8 elements in 16 comparisons with other algorithm. The algorithm is described in D.Knuth's "The art of computer programming", Vol 3, chapter 5.3.1. It is named merge insertion.

Lowest number of comparisons does not make this algorithm the fastest one. For example, Batcher odd–even mergesort with 19 comparisons easily outperforms merge insertion because it performs most comparisons in parallel.