🚀 go-pugleaf

In article <1992Nov11.161052.5552@panther.mot.com> asu@panther4.panther.mot.com (Russ Trotter) writes:
>I hate to jump on this seemingly runaway train but.... 
>
>In one of my classes, I remember the teacher saying that it
>had been proven that O(n log n) was the best one could do
>for _comparison_ based sorting...  Is this a more correct assertion?

The Order n log n is itself an approximation of (this is from memory with
out books close at hand) log n!  Check the text for any graduate level
class on algrithms for the derivation.

This raises the possibility of sorts faster than n log n.
Not lots (as such things go) faster, but somewhat faster.

>
>I don't know much (at all :) ) about Radix sort  (only how to spell it :) )
>so I can't be sure if it disproves the statement above.

Knuth has already been quoted here on this one, so I'll defer to the
expert.  In class the order is taught as k * n where k is the number of
radices.

The upper bound on k is log of the number of bits used to represent the
values.  Hence, as k increases, n log n behavior can be seen.


*THE* thing to remeber in all of this is that order notation is applicable
only as n rises.  Bubble sort has a very low overhead, it works well on
semi-sorted data, and most programmers can write it correctly.  That third
point should not be ignored.  Classical quicksort has to be modified to
keep from choking (O n*n )on sorted data.

My advice is: profile your code first, and worry about the slow parts that
profiling finds.


Neil Kirby