[Tim Peters, explains one of the new algorithm's surprisingly
effective moving parts]
[Chris Angelico
Thank you, great explanation. Can this be added to the source code if/when this algorithm gets implemented?
No ;-) While I enjoy trying to make hard things clear(er), I need to understand them inside out myself first, and I'm still not there with this algorithm. Even of what I do grok now, I cheated some to make that post simple. For example, if you read it carefully, you'll realize that the explanation I gave doesn't actually explain why the "x" * 100 example is correct: the explanation implicitly relied on that the left half the splitting (u) is at least as long as the right half (v). But that's not always the case (and, in particular, for "x" * 100, u is empty!). Tal Einat posted earlier that he was keen to try to work up a clear explanation, and I look forward to that. All the expositions I've found of this algorithm so far are hard to approach. The original paper is still the best I've seen. Everything I wrote was but a gloss on its Lemma 3.2.
I've learned all kinds of things from the huge block comments about timsort, list growth, and the like. They make great reading when you're trying to figure out how to explain things (or if you're a bored nerd browsing for curiosity's sake - that works too!).
Takes one to know one ;-) There's beauty and elegance in this algorithm, but they'll go unloved without explanations clear enough for the non-obsessed to follow.