7 Jun
2021
7 Jun
'21
8:53 p.m.
On Mon, Jun 7, 2021 at 11:20 AM Tim Peters
[Dan Stromberg
] ... 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.