How can we combine 8 elements with 16 comparisons?

Question

Ok, I asked a question about sorting a few days ago. I learned how to prove that the smallest number of comparisons by sorting 8 elements is 16, and I understood why. But my merge sorting algorithm has 17 comparisons, and in my case this is correct. To combine two sorted arrays with lengths x and y, we need (x + y) -1 comparisons, so in merge sorting we get 17 comparisons. But this should be possible with 16 comparisons, so .. how? where can I save this comparison 1).

Here is the image:

http://oeis.org/A001768

Thanks!

Answer 1

The OP provides clear evidence of the impossibility of sorting a merge of 8 elements with less than 17 comparisons. You can still sort 8 elements in 16 comparisons with another algorithm. The algorithm is described in D.Knuth, The Art of Computer Programming, Volume 3, Chapter 5.3.1. It is called a merge insert .

The smallest number of comparisons does not make this algorithm the fastest. For example, a Batcher odd-even mergesort with 19 comparisons will easily outperform a merge nest since it performs most comparisons in parallel.

Answer 2

You can get the smallest solution if you have an odd number of numbers to sort.

Answer 3

You can prove that 16 comparisons are not enough using all possible algorithms. To do this, you will need an "algorithm for generating algorithms."