[SciPy-dev] fast sorting of most numpy array types

[Charles R Harris]

On Thu, May 7, 2009 at 11:49 AM, Charles R Harris <charlesr.harris at gmail.com
> wrote:

>
>
> On Thu, May 7, 2009 at 8:32 AM, Andrew Schein <andrew at andrewschein.com>wrote:
>
>> Hi developers -
>>
>> I have recently release highly optimized type-specific C routines for
>> sorting arrays of numeric types:
>> **http://bitbucket.org/ais/usort/wiki/Home
>>
>> The code was motivated in part by noting that the numpy implementation of
>> sort appears to be a template-ized (over comparison) quicksort... and radix
>> sort is often the better choice.  Actually, it has been a few months since I
>> looked at the numpy source, so don't quote me.  The usort routines use a
>> variety of strategies depending on the size of the array: radix sort, quick
>> sort, insertion sort.
>>
>> I think the code could easily be incorporated in to numpy... and if there
>> is interest in accepting such a change, I might find time to do it myself.
>>
>
> Numpy has quicksort, mergesort, and heapsort and now and then someone on
> the list suggests adding radix sort. No doubt radix is suitable for certain
> types, char arrays seem a natural. But there are problems with byte order
> for the different integer types and floats can become complicated. And
> unlike quicksort radix sort isn't done inplace. So it isn't clear that a
> radix sort is the way to go for sorting in general but it could be useful in
> some places.
>
> Do you have some time results?
>

It isn't too hard to add sorts to numpy, so if you want to experiment with
code I can help you get started.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20090507/38d01733/attachment.html>