Sort comparison

[Ian Kelly]

On Mon, Apr 30, 2012 at 11:25 PM, Dan Stromberg <drsalists at 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