[Python-Dev] Drastically improving list.sort() for lists of strings/ints (original) (raw)

Petr Viktorin encukou at gmail.com
Sun Sep 11 18:58:45 EDT 2016

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.

More information about the Python-Dev mailing list