🚀 go-pugleaf

In a previous article, warwick@cs.uq.oz.au (Warwick Allison) 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.

Quoting from The Art of Computer Programming, Volume 3 (pp176-178):
"[r]adix sorting is usually more efficient than any other known
sorting method for internal sorting."

Speaking about his example program, Knuth says,
"A p-pass version of the program would take (11p-1)N+O(pM) units of
time." [p is the number of keys and M is the number of radix piles]

Finally, in the theoretical analysis of the algorithm (p178), Knuth
finds that, if p=2 and M > sqrt(N), the average sorting time is O(N)
instead of order NlogN.  

|> >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 !!!!!!
Better check your references.

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

Better yet, how about renaming it to "alt.games.programmer.cant.read"?

DOS programmers are "real" programmers?  (snicker)  (I'm only kidding,
guys!)

|> Come on people, games programming is definately an art-form, but we
|> really must learn to hold our mallet and chisel correctly.  (Of course,
|> asm programmers only need to learn to hold the chisel, since they use
|> their head to supply the force).

Yep, games are an art form.  So is the process of not reinventing the
wheel. It involves a bit of research. Maybe you should spend a little
more time at the local library?  :)

Assembly programmers don't use mallets.  They use toothpicks and
simply hit them 90,000 times in the same time a mallet could strike
once.  This works really well until they discover that they're
striking the wrong piece of rock...

|> Warwick
dank