On Mon, Jun 7, 2021 at 11:20 AM Tim Peters <tim.peters@gmail.com> wrote:
[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

Thanks Tim.

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.