Sort comparison

[Ian Kelly]

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.