🚀 go-pugleaf

Warwick Allison (warwick@cs.uq.oz.au) wrote:
: >A radix sort has a time complexity of O(N), which means that it
: >operates in linear time on N units of data.
: Gee, I'm sure the theoreticians would LOVE to see the algorithm,
: since it has been PROVED long ago that sorting takes O(N log N)
: time OPTIMALLY.

Maybe you should go back and check this. If the theorem exists at all,
it will only apply for a (very small) sub-class of possible
algorithms. The radix sort DOES run in N. While the radix sort is a
fairly restricted sort, you can (fairly easily) construct an alogrithm
that will beat N log N in the limit. (look up Knuth on the subject. He
has more than a few words to say about it).

On a parallel machine, I can sort N numbers in log N time.
 
: >This integer may then be
: >represented as the path in a binary tree, with the higher order
: >bits represented as paths near the root and the lower order bits as
: >paths near the leaves.
: Guess what?  The number of bits will be of the order LOG N !!!!!!

No it won't. The running time of the algorithm is N * M, where N is
the number of items of data, and M is the radix width.

1/2 a seconds thought will reveal to you that M is a constant, and
thus the running time is.... O(n).
 
: Let's rename this group to rec.games.!programmer, and succumb to the
: community's belief that "games programmers" aren't real programmers
: at all.  All the Windows programmers and DOS device driver programmers
: can then cross there arms smugly and shake their heads at us non-
: programmers, who can only write GAMES, saying "gee, they've discovered
: SORTING"...

Looks like you haven't quite got the hang of it all yet... ;) Just
FYI, sorting is still considered a rather hotly researched subject. 
 

: Warwick