Thank you, Vincent!  I very much enjoyed - and appreciated - your paper I referenced at the start.  Way back when, I thought I had a proof of O(N log N), but never wrote it up because some details weren't convincing - even to me ;-) .  Then I had to move on to other things, and never got back to it.  I was probably mistaken.  So it was delightful to see your elegant proof of that, and even more.

I'm attaching a new runstack.py that includes code modeling your new adaptive Shivers strategy.  Like all these approximations, it has its own "bad cases" on smallish inputs.  Based on the specific cases this code runs, powersort remains in a category of its own, with timsort, twomerge, and shivers roughly tied on _average_ merge cost.

Part of the reason, I suspect:  powersort is the only strategy here that's always optimal for 3-run cases.  Which it buys at the cost of never merging the run just discovered (unless it's the last run in the array).  For example, in

    31, 16, 1

twomerge and shivers merge 31 and 16 first, before seeing 1, which is "far from" optimal.  timsort and powersort merge 16 and 1 first, although that's by design in powersort and by luck in timsort.  In

    16, 31, 1
    
only powersort does the best thing (note: runstack.py doesn't model peeksort; I'm sure it would merge 31 and 1 first on that too).

I care about small-number-of-runs because real-life Python lists aren't asymptotic in nature ;-)  People deliberately construct lists with a small number of runs now before sorting, because they know Python's sort can exploit that.  For many other cases, all runs are artificially forced to length `minrun`, and then any scheme at all that approximates balanced merging is about as good as any other.

What I can't know before we time things is whether order-of-merging makes a measurable difference in real life, and whether powersort's possible delay in merging the most recent run has bad cache effects that overwhelm its smaller "merge cost".

In any case, I'm keen to replace timsort's merge-order strategy with _something_ that's much easier to analyze.  The makes your Shivers variant and powersort the only two real contenders now.  It seems quite remarkable that the Shivers variant has such good asymptotics!  It's certainly the easiest to modify Python's C code to implement (straightforward edits in a single function).