[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. 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-leave@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/