[Python-ideas] Optimizing list.sort() by checking type in advance

[Franklin? Lee]

On Mon, Oct 10, 2016 at 11:29 PM, Elliot Gorokhovsky
<elliot.gorokhovsky at gmail.com> wrote:
>> Note that when Python's current sort was adopted in Java, they still kept
>> a quicksort variant for "unboxed" builtin types.  The adaptive merge sort
>> incurs many overheads that often cost more than they save unless comparisons
>> are in fact very expensive compared to the cost of pointer copying (and in
>> Java comparison of unboxed types is cheap).  Indeed, for native numeric
>> types, where comparison is dirt cheap, quicksort generally runs faster than
>> mergesort despite that the former does _more_ comparisons (because mergesort
>> does so much more pointer-copying).
>
>
> Ya, I think this may be a good approach for floats: if the list is all
> floats, just copy all the floats into a seperate array, use the standard
> library quicksort, and then construct a sorted PyObject* array. Like maybe
> set up a struct { PyObject* payload, float key } type of deal. This wouldn't
> work for strings (unicode is scary), and probably not for ints (one would
> have to check that all the ints are within C long bounds). Though on the
> other hand perhaps this would be too expensive?

I happened onto a page talking about float radix sort, and thought of
this thread.

Here it is: http://stereopsis.com/radix.html
The author claimed an 8x speedup, though the test was done nearly
fifteen years ago.

I was unsure about posting publicly, because it's not as if an even
faster float sort would help decide whether specialized sorts are
worth adding to CPython. I'm posting for history.