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

[Charles R Harris]

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?

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