Home Original page

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

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