Sort comparison

[Dan Stromberg]

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?

I thought that on a log-log graph, a straight line was still a straight
line, but it's compressed at one end.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20120501/e67fd95d/attachment-0001.html>