[Numpy-discussion] speed problem with Numeric sort

[Tim Hochberg]

Chris Barker writes:

[He doesn't get a slowdown with Numeric 20.0.0 on Linux]
> So whatever it was may have been fixed (or be a strange platform
> dependence).
[SNIP]

It must just be the cleverness of your platform's qsort. Numeric delegates
sorting to qsort and running qsort on Windows 2000 with Numeric 20.0.0 I get
similar values to Bethold's. Also some rather naive calculations for the
complexity of quicksort on a list of n items with k distinct values gives me
O((log(n/k) + (n/k)) * n). That's probably not exactly right, but it matches
the timings I get pretty well.



-tim