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

Mark Dickinson dickinsm at gmail.com
Sun Sep 11 14:58:08 EDT 2016

On Sun, Sep 11, 2016 at 7:43 PM, Elliot Gorokhovsky <elliot.gorokhovsky 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.)

Apart from the cases already mentioned by Chris, one of the situations you'll want to include in the benchmarks is the case of a list that's already almost sorted (e.g., an already sorted list with a few extra unsorted elements appended). This is a case that does arise in practice, and that Timsort performs particularly well on.

-- Mark

More information about the Python-Dev mailing list