June 19, 2001
6:29 p.m.
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