🚀 go-pugleaf

Warwick Allison (warwick@cs.uq.oz.au) wrote:
: oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes:
: >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.

The whole idea of the radix sort is that it sorts data of a constant
width. So for a list of data of CONSTANT WIDTH!!! It will run in
O(n). The real running time is N * data width. If I sort numbers on a
32 bit machine, it will be 32N, regardless of what my numbers are (as
long as they fit in 32 bits), and regardless of how many there are. It
certainly doesn't increase of the log of the numbers. Sorting 50
numbers will take exactly twice as long as sorting 25 numbers. The
time taken to sort is linear.
 
: 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.

Try sorting 50,000 numbers in the range 0-7 (yes, this is a real case.
Sorting unique numbers is NOT realistic). The running time is 3 *
50,000 not, 50,000 * 16. Here's the really neat bit. If I sort 100,000
of these numbers it will take 100,000 * 3, not 100,000 * 17!!!!

In other words, the sort time is LINEAR on the number of numbers, NOT
NlogN on the numbers. If I sort twice as many numbers it will take
EXACTLY twice as long.

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

Sigh. Who said it was?? Radix sort is a niche algorithm. If you are
sorting long of fixed length bit strings, it will run in O(n), and
will run faster than a quicksort. (before you open you mouth again,
why don't you run some tests to check this for yourself. If so a
little trivial math and work out expected operation counts.)

It is not any good for sorting strings, or any other general data. If
you want to sort 50 numbers in 0-255 it will run in 50 * 8 * c1. If
you use a quicksort it will run in 50 * 6 * c2.

c1, c2 being constants dependant on impementation. Now look at some
code for these algorithms, and work out relative values of c1, c2.
(i.e. look at number of intstructions in inner loop, and instruction
costs). Quicksort is approx 3 - 20 times more expensive. (depending on
how expensive you rate a function call). So for this particular app, a
radix sort will run faster.

: Warwick