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 inputs.
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.