On Mon, Jun 7, 2021 at 11:20 AM Tim Peters <tim.pet...@gmail.com> wrote:
> [Dan Stromberg <drsali...@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.
_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-le...@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/7K6WWWAYEGRNQOW47DQE45FFNSKZSG7X/ Code of Conduct: http://python.org/psf/codeofconduct/