🚀 go-pugleaf

In article <10991@uqcspe.cs.uq.oz.au> warwick@cs.uq.oz.au writes:
)>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.

   You are invited to read any decent book on sorting before posting, next 
time.

   O(n logn) is optimal for arbitrary things. In some special cases,
you can do better. Radix sort fits one of these special cases.



)>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 !!!!!!

   Number of bits will be log P where P is the largest integer. 
That doesn't have to have much to do with the number of items.
(hint: sort the government debt of the top 15 debtor nations, 
values expressed in lire. What is N? What is P?)

)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"...
   no, "They haven't a CLUE about SORTING" as evidenced by many posts.