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
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 !!
Amazing article! This really helped me wrap my head around the recursive nature of main chain sorting!! <3
One tiny thing that might help people starting the project:
It can be a bit overkill to track every single element in the main chain just to ensure that
b_xis never compared witha_x. The Ford-Johnson algorithm only requires that each insertion happens using at mostkcomparisons.You can still achieve the maximum allowed comparisons by inserting into a "naive" main chain -- you don't need to care whether the element is an
aor ab, etc. I wrote about this approach here ;)Thank you for you feedback!
Yep. I think tbh that even the recursion is not mandatory for this algorithm, as long as the sorting principle is the same and the number of comparisons is under the threshold. Great to see alternative approaches.
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!
Ineresting algorithm, thx for detailed describing.
Thank you very much. It was very helpful for me!
thanks man keep going
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.