Take the 2-minute tour ×

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:

enter image description here



share|improve this question
And this is that previous question –  Henk Holterman Dec 31 '11 at 12:22
You state that you already know "how to prove that ... is 16". Your proof should be able to answer this question. –  Henk Holterman Dec 31 '11 at 12:25
i mean i expect that theoretically it is possible –  haemhweg Dec 31 '11 at 12:33
The "least" number of comparisons required to sort 8 elements with a merge sort is something less than 16. For example, if your two 4-element subarrays are [0, 1, 2, 3] and [4, 5, 6, 7], then it will take only four comparisons to merge them. After the fourth comparison the first subarray is empty and you can just copy the second subarray--no item comparisons required. –  Jim Mischel Dec 31 '11 at 14:59
Using radix sort or some other non-comparison sort algorithms you won't need to compare anymore. –  Lưu Vĩnh Phúc Aug 3 '13 at 11:46

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
very best answer.. there is a whole paragraph for my problem with "the best worst case" for number of comparisons. –  haemhweg Jan 2 '12 at 10:44

You can only get the least solution when you have an odd amount of numbers to sort.

share|improve this answer
How so? It's not obvious to me. –  Dialecticus Dec 31 '11 at 12:29
Because at the lowest level you save a comparison. Your base would be like 2 - 2 - 2 - 1 with 7 elements. Thus you will not need to compare the last couple (since it isn't a couple). –  ChristopherS Dec 31 '11 at 12:31

You could prove that 16 comparisons is not enough by trying all possible algorithms. You would need and "algorithm generating algorithm" for this.

share|improve this answer

Your Answer


