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.
-- http://mail.python.org/mailman/listinfo/python-list
