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

[Raymond Hettinger]

> On Sep 11, 2016, at 11:58 AM, Mark Dickinson <dickinsm at gmail.com> wrote:
> 
>> So I suppose the thing to do is to benchmark stable radix sort against timsort and see if it's still worth it.
> 
> Agreed; it would definitely be interesting to see benchmarks for the
> two-array stable sort as well as the American Flag unstable sort.
> (Indeed, I think it would be hard to move the proposal forward without
> such benchmarks.)

In the meantime, can I suggest moving this discussion to python-ideas.

There are many practical issues to be addressed:  
* sort stability
* detecting whether you're dealing with a list of strings
* working with unicode rather than inputs limited to a one-byte alphabet
* dealing with the multiple compact forms of unicode strings (i.e. complex internal representation)
* avoiding degenerate cases
* cache performance

The referenced article tells us that "troubles with radix sort are in implementation, not in conception".


Raymond