Sort comparison

[Dan Stromberg]

A while back I did a sort algorithm runtime comparison for a variety of
sorting algorithms, and then mostly sat on it.

Recently, I got into a discussion with someone on stackoverflow about the
running time of radix sort.

I realize it's commonly said that radixsort is n*k rather than n*log(n).
I've been making that case that in real life, frequently k==log(n).

Anyway, here's the comparison, with code and graph:
http://stromberg.dnsalias.org/~strombrg/sort-comparison/

(It's done in Pure python and Cython, with a little m4).

Interesting, BTW, that an unstable quicksort in Cython was approaching
timsort as a C extension module in performance, even though timsort in
Cython wasn't that performant.  It makes one wonder if a highly optimized
quicksort as a C extension module wouldn't outperform timsort in the
standard library.

Yes, I know, we've committed to keeping list_.sort() stable now, and
quicksort normally isn't stable.

Also, before timsort, did CPython use quicksort?  I'd be a little surprised
if it hadn't, since people used to say quicksort was the best thing around
in practice.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20120430/e580e149/attachment-0001.html>