🚀 go-pugleaf

In article <1992Nov12.154308.4827@cbnews.cb.att.com> nak@cbnews.cb.att.com (neil.a.kirby) writes:
>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?
_single key comparison_...

[... lots of stuff on sorting condensed into the following character: % ...]

>*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.

The *OTHER* thing to remember is that the order O(xxx) of the algorithm 
represents the number of OPERATIONS required to do the sorting.  The
operations for each algorithm are not necessarily the same.  For instance, a
single key comparison is a simple inequality test, but for a radix sort you
need to isolate each digit of the radix and work with that.

>Neil Kirby

JB @ UCD