Did this project help you? Give it a 🌟!
This is an exercise from the 42 school curriculum.
Version: 2.2 of C++ Module 09.
The implementation follows carefully the description given in the book "The Art of Computer Programming" by Donald Knuth. If you find any mistake, please let me know.
The program's test suite outputs a brief time benchmark comparing the time performance of std::vector and std::deque with my implementation. However, absolute time measurements are not particularly relevant since the Ford-Johnson algorithm is designed to minimize the number of comparisons rather than optimize execution time.
While the implementation does not measure the actual number of comparisons, the sorting behavior should align with the Ford-Johnson algorithm's theoretical description.
See architecture.md for detailed diagrams of the project structure and the Ford-Johnson algorithm flow.
- The Art of Computer Programming, Volume 3: Sorting and Searching by Donald Knuth (Section 5.3.1, pages 183-186). This is the original description of the algorithm. However, the explanations are rather terse and not very pedagogical — the resources below are more accessible.
- Human explanation and step-by-step visualisation of the Ford-Johnson algorithm.
- The Morwenn implementation. An excellent C++11 implementation. It does many optimizations, which make code more efficient but less clean. As this algorithm is, in all cases not fast at all (as conceded by the author itself in its last updated version), I choose to focus my implementation on a cleaner and more pedagogical code.
- Wikipedia: Merge-insertion sort
- Scientific paper to go further: On the Average Case of MergeInsertion.