🚀 go-pugleaf

In article <11018@uqcspe.cs.uq.oz.au>, warwick@cs.uq.oz.au
  (Warwick Allison) says:
>
>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.

There seems to me to be some confusion here.  If M is allowed to grow,
then the proper measure of the length of the input to a sorting algorithm
is not N, but N*M = N*log(R).  So if Radix sort takes N*M time, then the
time would still be a linear function of the length of the input.  It only
makes sense to measure the length of the input to a sorting algorithm by
N alone if M is taken to be bounded.  Extreme Example:  If we don't keep M
bounded, then two numbers can't be sorted in constant time beacuse the
amount of time needed to compare them is a function of M.  I hope this
helps.

Carl Cotner
cxc19@psuvm.psu.edu