I finally put my whiteboard back up that’s been down since before Covid. It still had scribblings of a novel merge sort with lower space overhead that turned out to be an artifact of non-representative sample inputs. As Bletchley Park taught us, humans are terrible at randomness.
No piece of software replicates the experience of having a board to write things on (or magnet things to, if yours is ferromagnetic like mine). The ones that come closest, that money is better spent on something else.
Typically you merge a block A and block B into a new block C that has the same length as A + B. I thought I saw a way to use a few extra pointers and some swap operations to turn A and B into C by chipping away at their left ends, and still being a stable sort. The examples I came up with worked and confirmation bias took over. But in real data there were combinations of runs that broke the algorithm.
No piece of software replicates the experience of having a board to write things on (or magnet things to, if yours is ferromagnetic like mine). The ones that come closest, that money is better spent on something else.