[Dan Stromberg <drsalists@gmail.com>]
> ...
> Timsort added the innovation of making mergesort in-place, plus a little
> (though already common) O(*n^2) sorting for small sublists.

Actually, both were already very common in mergesorts. "timsort" is
much more a work of engineering than of insight ;-) That is, it
combined many pre-existing ideas, but pushed them hard, and got them
to work smoothly together.

The most novel part is "galloping" to vastly cut the number of
comparisons needed in many real-world cases of partially ordered
inputs.