Menu
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!
636
The runtime of merge sort is given by the formula, T(n) = 2*T(n/2) + n, where T(n) is the number of comparisons required to sort a list containing n elements. The algorithm, repeatly, reduces the problem size by half (n/2) each time it splits the unsorted list of numbers into two sublists.
The minimum number of comparisons for the merge step is approximately n/2 (which by the way is still O(n) ), assuming a sane implementation once one of the lists has been fully traversed.
Explanation: To merge two lists of size m and n, we need to do m+n-1 comparisons in worst case.
4.
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.
122
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
