Correction Needed: Incorrect Usage of Merge Insertion Sort in Step 4

[usatie]

It appears that the current implementation deviates from the Ford Johnson's merge insertion sort algorithm at Step 4, where a different sorting technique, namely insert sort, is utilized instead. I would like to propose a correction to align with the intended usage of the algorithm.

In the README or relevant documentation of your repository, I came across the following excerpt explaining Step 4:

Step 4: Sort the Pair Sequence by its greater value The next step in FJMI is to recursively sort all the pairs by their largest element. In this implementation, we use ‘sort_by_larger_value’, which receives the array (which has already been split into pairs, and each pair sorted itself) and uses a modified recursive insertion sort (using functions ‘insertion_sort_pairs’ and ‘insert’) that perform this action. This leaves the array sorted by the greater value in each pair.

According to my understanding of the Ford Johnson's merge insertion sort algorithm, it necessitates the recursive usage of merge insertion sort at Step 4, rather than insert sort. The utilization of merge insertion sort ensures the algorithm's correctness and efficiency.

[CodeOptimist]

Hi @usatie ! I just saw this since I watch this repository. My first thought was, "Oh, Shun should look at my implementation." Then I realized I never published it. 🤦‍♂️ But now it is. 😊

https://github.com/CodeOptimist/ford-johnson-algorithm/blob/main/main.py Note the tests: https://github.com/CodeOptimist/ford-johnson-algorithm/blob/main/tests.py, which is the only reason I believe it to be correct. 😅

[usatie]

@CodeOptimist Wow, thanks a lot! I have been curious about your implementation since I saw you on the previous issue 😄

I must say, I am truly impressed by the simplicity of your implementation. Comparatively, my own implementation for a similar project in C++ was significantly more complex. Your code has certainly piqued my interest. https://github.com/usatie/CPP09/blob/master/ex02/src/PMergeMe.hpp

Once again, I appreciate your willingness to share your implementation and for shedding light on its simplicity. It serves as a great learning opportunity for me and others who may come across your repository.

[A-Thierry]

@PunkChameleon I have noted two unrelated issues with recursion in the code:

1. insertion sort is implemented recursively. Isn't iterative better for insert ? That one won't matter once the recursive call this issue is about is fixed.

2. the jacobsthal sequence is stored in an array for later use, but the elements of that sequence are computed recursively instead of using the previously stored values.

@usatie Hi, 42 Japan !!!

@CodeOptimist Really nice implementation. Impressed as well !

[PunkChameleon]

@usatie @A-Thierry thank you for reviewing and checking this out! The feedback is great! If you want to, it would be amazing if you submitted a PR if you wanted to take a crack at changing or updating it!

[PunkChameleon]

Hey @usatie @A-Thierry - just coming back to this repo after a long while. You ever get a chance to review your work to see if we can merge in? Either way no worries!