Thank you for creating this great guide, it's very well explained and visualized and easy to follow.
However, if you implement the logic following this guide, and also implement a counter to count the number of comparisons, you will find that you have too many comparisons. For example, it is stated in Art Of Computer Programming, Vol. 3 on page 184, that for sorting 21 numbers, merge insertion will take at most 66 comparisons. However, it took up to 70 comparisons with my implementation following this guide.
I found out that the issue lies in the insertion order. You wrote that if we have no more elements corresponding to a jacobsthal number in the pend, we have to sort the remaining elements in order, and that the 'odd element' should always be inserted last. This is incorrect. This became clear to me after looking into another paper which was also referenced in the 'Art of Computer Programming' book: A Tournament Problem
Here we find a perfect example:
You can imagine A-J to be the main chain, and all the dots with the numbers under them would be the pend elements. (in this case b2 - b10). You will notice that the 'odd element' has no special significance here, it is not inserted last.
Note that the 'Order of Insertion' is clearly specified in that example:
b3, b2, b5, b4, b10, b9, b8, b7, b6
This means that we can simply add the 'odd element' into the pend and insert the pend elements back into the main chain according to the jacobsthal numbers. Once we have no more elements that correspond to a jacobsthal number in the pend, we simply insert the remaining elements in reverse order starting at the last one (b10 in this case).
Here is another example to make it more clear:
Pend: b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15, b16
Main: b1, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15
insertion order: b3, b2, b5, b4, b11, b10, b9, b8, b7, b6, b16, b15, b14, b13, b12
And with this change, you will never exceed 66 comparisons for sorting 21 numbers. In the 'Art of Computer Programming' book, on page 186 you will find a table listing the maximum number of comparisons for sorting 1-33 numbers in the worst case, so you can double check and verify that you never exceed any of those. (There is also a formula to calculate the maximum for any given sequence length)
Thank you for creating this great guide, it's very well explained and visualized and easy to follow.
However, if you implement the logic following this guide, and also implement a counter to count the number of comparisons, you will find that you have too many comparisons. For example, it is stated in Art Of Computer Programming, Vol. 3 on page 184, that for sorting 21 numbers, merge insertion will take at most 66 comparisons. However, it took up to 70 comparisons with my implementation following this guide.
I found out that the issue lies in the insertion order. You wrote that if we have no more elements corresponding to a jacobsthal number in the pend, we have to sort the remaining elements in order, and that the 'odd element' should always be inserted last. This is incorrect. This became clear to me after looking into another paper which was also referenced in the 'Art of Computer Programming' book: A Tournament Problem
Here we find a perfect example:
You can imagine A-J to be the main chain, and all the dots with the numbers under them would be the pend elements. (in this case b2 - b10). You will notice that the 'odd element' has no special significance here, it is not inserted last.
Note that the 'Order of Insertion' is clearly specified in that example:
b3, b2, b5, b4, b10, b9, b8, b7, b6
This means that we can simply add the 'odd element' into the pend and insert the pend elements back into the main chain according to the jacobsthal numbers. Once we have no more elements that correspond to a jacobsthal number in the pend, we simply insert the remaining elements in reverse order starting at the last one (b10 in this case).
Here is another example to make it more clear:
Pend: b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15, b16
Main: b1, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15
insertion order: b3, b2, b5, b4, b11, b10, b9, b8, b7, b6, b16, b15, b14, b13, b12
And with this change, you will never exceed 66 comparisons for sorting 21 numbers. In the 'Art of Computer Programming' book, on page 186 you will find a table listing the maximum number of comparisons for sorting 1-33 numbers in the worst case, so you can double check and verify that you never exceed any of those. (There is also a formula to calculate the maximum for any given sequence length)
Great details and resources, thank you so much man !!
Hello!
I finally fixed the mistakes in the article and mentioned you.
Thank you for the detailed feedback.
Indeed, you are totally right. My mistake was that I made an odd number 'special'.
When I'll have time, I'll review the article and update it.