On Mon, Oct 10, 2016 at 11:29 PM, Elliot Gorokhovsky
<elliot.gorokhov...@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.
_______________________________________________
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/
