9

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

http://oeis.org/A001768

Thanks!

Uwe Keim
  • 39,551
  • 56
  • 175
  • 291
nakajuice
  • 691
  • 1
  • 11
  • 23
  • 1
    And this is that [previous question](http://stackoverflow.com/q/8673860/60761) – H H 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. – H H Dec 31 '11 at 12:25
  • i mean i expect that theoretically it is possible – nakajuice Dec 31 '11 at 12:33
  • 1
    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. – phuclv Aug 03 '13 at 11:46

3 Answers3

6

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.

Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98
  • very best answer.. there is a whole paragraph for my problem with "the best worst case" for number of comparisons. – nakajuice Jan 02 '12 at 10:44
3

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

ChristopherS
  • 853
  • 4
  • 16
1

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

Dialecticus
  • 16,400
  • 7
  • 43
  • 103