Sort comparison

[Dan Stromberg]

On Tue, May 1, 2012 at 11:52 AM, Ian Kelly <ian.g.kelly at gmail.com> wrote:

> On Tue, May 1, 2012 at 12:00 PM, Dan Stromberg <drsalists at gmail.com>
> wrote:
> >
> > On Tue, May 1, 2012 at 12:21 AM, Ian Kelly <ian.g.kelly at gmail.com>
> wrote:
> >>
> >> 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.
> >
> > Thank you for your comment.
> >
> > Do you have a suggestion for a better type of graph - or other
> > linearity/nonlinearity test?
>
> An ordinary linear-scale graph.  It will only show the highest order
> of magnitude in any detail, but for determining asymptotic behavior
> that's the most interesting part anyway.  O(n) should look like a
> straight line, and O(n log n) should curve up with a gradually
> increasing slope.  Alternatively, calculate regressions and compare
> the goodness of fit.
>
> > I thought that on a log-log graph, a straight line was still a straight
> > line, but it's compressed at one end.
>
> The key characteristic of a log-log plot is that any curve y = ax ** b
> will appear as a straight line with a slope of b.  So a linear curve
> will be a straight line with a slope of 1.  A O(n log n) curve will
> converge to a straight line with a slope of 1 as n approaches
> infinity.
>

Thanks for the info.

I actually feel like both the log-log graph and the linear-linear graph,
tell an interesting but different part of the story, so I've kept the
log-log graph and added a linear-linear graph.

I also added a linear-line to the linear-linear graph, for the sake of
comparison.

You can see that radix sort is falling between mergesort and quicksort
(both nlogn on average), and radix sort is coming up almost parallel to
mergesort.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20120501/5624663c/attachment-0001.html>