[Dan Stromberg <email@example.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
Python itself is a great language, but in part it was your good-natured and well-reasoned posts about Python that got me into Python instead of OCaml.