ProjectsSystems, network & algorithms
CPP Module 09
Ford-Johnson sort and a visualiser
- Period
- Sept 2025 – Oct 2025
- Context
- 42 curriculum
- Team
- solo
- Grade
- 100/100 · outstanding ×3
- C++
- Algorithms
- Object-oriented programming
- Mathematics
- Tester
The last module of the C++ piscine, built around STL containers. Its final exercise asks for the Ford-Johnson sort, an algorithm that tries to sort with as few comparisons as possible.
The exercises
Three exercises, three containers: a bitcoin exchange-rate converter that looks up the closest date in a std::map, a reverse Polish notation calculator on a stack, and the Ford-Johnson sort, applied to two different containers to compare their performance.
Ford-Johnson
Numbers are grouped in pairs, and each pair is compared: the larger one goes into the “main chain”, the smaller one waits. The main chain is sorted recursively with the same algorithm. Then each small element is inserted with a binary search.
The trick is the insertion order: Jacobsthal numbers (1, 3, 5, 11, 21…) mark groups that are inserted from the end backwards. Each search then runs over a range whose size is just under a power of two, which saves comparisons.
The visualiser
For fun, I added a terminal visualiser, in C++23 with the FTXUI library: it runs the program with different parameters and shows the results, to see how the two containers behave depending on the input size.
What I took away
- An algorithm can be optimal in comparisons without being the fastest in practice.
- The choice of container matters as much as the algorithm.