I've an idea for a merge sort variant that's been rattling around my head for a while.
The idea is that sorting is broken up into two phase: run identification and merging. This has some similarities to Timsort, but it's not quite the same thing.
In the run identification phase, runs are identified and recorded. There is some deperturbation to try an identify the longest runs possible near the potential end of runs where if the next element, x[i], is less than x[i-1] and x[i-2], it is swapped with x[i-1].
If no run longer than N can be identified since the last identified run by M elements, those M elements are sorted using insertion sort to create a run.
When we have a list of runs, we start merging adjacent pairs of runs, starting with the smallest adjacent pairs.