🚀 go-pugleaf

dank@calvin.usc.edu (Dan King) writes:

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

Is that the first edition (1968), or second edition (1973).
I hope the references haven't dated too much :-).

Seriously, it's these exact statement that I'm arguing against.  Saying that ANY
algorithm for sorting is the best, or "usually more efficient than any other" is
simply crazy.  Each algorithm has strengths and weaknesses.  Radix sort isn't
even APPLICABLE in most cases.


>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]

ie. if p is too large, forget it.  too large = O(N)... or even O(sqrt(N)).
(where N is the EXPECTED number of items for sorting)

--
Warwick
--
  _-_|\      warwick@cs.uq.oz.au            /Disclaimer:
 /     * <-- Computer Science Department,  /  
 \_.-._/     University of Queensland,    /   C references are NULL && void*
      v      Brisbane, Australia.        /