On Mon, Apr 30, 2012 at 11:25 PM, Dan Stromberg <drsali...@gmail.com> wrote: > > 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 can be difficult to distinguish O(n) from O(n log n) on a log-log plot, so I don't think that graph makes your point very well. > 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. Based on a little googling, it was quicksort prior to 1.5.2, then it was changed to a highly optimized samplesort (a quicksort variant) / insertion sort hybrid until the current timsort was implemented in 2.3. Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
