Ford-Johnson sorting algorithm, or merge-insertion sort, is not a very well known or popular algorithm, which is optimised for making the least amo...
For further actions, you may consider blocking this person and/or reporting abuse
Hey @emuminov great article! But just like @bewerner I also implemented some changes to your existing code so that the nums of comparisons match those mentioned in the book. Would you be open to reviewing them?
Hello! Thank you. Yes, would love to see the changes. I can include them into the code and credit you and @bewerner if you want.
Didn't receive a reply, but still fixed this little issue in my code.
Oh, my bad didn't get notice your reply. Anyway, I just looked through your code and think it's really similar to what I have. I would like to propose some minor simplifications on top of that and have created an issue on ur repo!
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)
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.
Great details and resources, thank you so much man !!
Ineresting algorithm, thx for detailed describing.
thanks man keep going
Thank you very much. It was very helpful for me!
Excellent explanation, thank you so much, you really helped me here. I just spotted a little mistake you made : the jacobsthal formula is (2^(n+1) - -1^n) / 3 and not (2^(n+1) + -1^n) / 3.
Thank you for the feedback.
The presented formula was taken from the Knuth's book, on the next page right after the algorithm was introduced.