🚀 go-pugleaf

oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes:

>Warwick Allison (warwick@cs.uq.oz.au) wrote:
>: >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).

BOGUS!  M is NOT a constant.  Sure, for values between 000 and 999
it is the constant 3, and for values between 000000 and 999999 it
is the constant 6 [assuming decimal radix sort, for simplicity].
and for values in the range 000000000 to 999999999 it will be 9.

ie. for a range of R values, M = log R.  Now, I suggest that for
general purposes, R will be larger than N.  For example, R will
be 2^32 (ie. integers), while N will be, say 10000000.

Basically, what it boils down to is that you MIGHT be able to
do better with a Radix sort, provided your data only has a small
range, but Radix sort is NOT in general better than Quicksort,
or Merge sort.

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