<br>A while back I did a sort algorithm runtime comparison for a variety of sorting algorithms, and then mostly sat on it.<br><br>Recently, I got into a discussion with someone on stackoverflow about the running time of radix sort.<br>
<br>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).<br><br>Anyway, here's the comparison, with code and graph: <a href="http://stromberg.dnsalias.org/~strombrg/sort-comparison/">http://stromberg.dnsalias.org/~strombrg/sort-comparison/</a><br>
<br>(It's done in Pure python and Cython, with a little m4).<br><br>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.<br>
<br>Yes, I know, we've committed to keeping list_.sort() stable now, and quicksort normally isn't stable.<br><br>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.<br>
<br>