On 09/11/2016 10:48 PM, Terry Reedy wrote:
[...]
Second, with respect to timsort in particular: timsort is designed to
exploit structure and run faster than O(n*logn) in special cases. If a
list is already sorted, timsort will do one O(n) scan and stop. Any
radix sort will take several times longer. If a list is reverse sorted,
timsort will do one O(n) scan and do an O(n) reverse. If a list is the
concatenation of two sorted lists, timsort will find the two sorted
sublists and merge them. If a sorted list has unsorted items appended
to the end, timsort will sort the appended items and then do a merge. I
expect any radix sort to be slower for all these cases. Tim Peters
somewhere documented his experiments and results with various special
but plausible cases of non-randomness.
That write-up is included in Python source:
https://github.com/python/cpython/blob/master/Objects/listsort.txt
A good read if you want to know what sort of thinking, benchmarking, and
justification should go into a new sorting algorithm.
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
https://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
