[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. I took that idea from (as briefly explained in listsort.txt) papers seeking to speed real-life unions and intersections of sorted lists, presumably in database implementations. I later discovered that the idea had already been applied to a mergesort, as noted in a paper by McIlroy (cited in listsort.txt) - but the paper didn't give any details, and best I can tell he never published his code. WIthout that, timsort wouldn't have been worth the bother of writing - it was generally no faster than Python's prior sort implementation on randomly-ordered inputs, and is quite a large pile of code. But many cases of real-world inputs do have significant pre-existing order of some kind, where even a "perfect" quicksort (always picks _the_ median as the partition pivot) remains O(n log n) but timsort O(n). Curiously, though, it was the only implementation ever tried of a mergesort-based algorithm that wasn't notably _slower_ on randomly-ordered inputs than Python's prior "samplesort" algorithm (like quicksort but with a very high-quality guess for the median element based on recursively sample-sorting a largish random sample). _______________________________________________ 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/Y22TRSA5I4JCNC6GRBX7QZYF4MLGPCYK/ Code of Conduct: http://python.org/psf/codeofconduct/
