🚀 go-pugleaf

Warwick Allison (warwick@cs.uq.oz.au) wrote:
: foo@netcom.com (Mark Hall) writes:
: >warwick@cs.uq.oz.au writes:
: 
: >   O(n logn) is optimal for arbitrary things. In some special cases,
: >you can do better. Radix sort fits one of these special cases.
: >)Guess what?  The number of bits will be of the order LOG N !!!!!!
: >   Number of bits will be log P where P is the largest integer. 
: >That doesn't have to have much to do with the number of items.
: >(hint: sort the government debt of the top 15 debtor nations, 
: >values expressed in lire. What is N? What is P?)
: 
: You're fighting against yourself here.  P will be GREATER than N, but
: once passed through an appropriate O(1) hashing function, the number
: of bits will still be of the order LOG N.  ie. O(log2 15), ie. 4, ie.
: you need a neato hashing function that maps those debts to unique,
: order preserving values in the range 0..15.

Nope. You are loseing it a little here. If you have 5,000,000 items of
32 bit data, it will take 32 passes over the 5,000,000 items for a
running time that is  ~5,000,000 * 32. If you take 1,000 item, it will
run in 1,000 * 32. I.e. looking very crefully you notice that it is...
	32 * N.
which is
	O(n).

: See?
Nope.
 
: Point is, Radix sort ONLY WORKS when there the number of distinct (unique)
: values in the unsorted data is less than O(log N).  If your data has
: that characteristic, go ahead and use Radix sort.  Such data is rare,
: however.  BUT, Radix sort can be very cheaply implemented on computers,
: reducing the constant - that's the real reason it is faster in some
: cases.

Radix sort works where the data can be reduce to a fixed length
bitstring. That data is very common. Any list of number can be sorted
useing radix sort.

A list of VARIABLE length strings on the other hand, couldn't be
sorted, as the concept of a LSB doesn't make sense.

In general, any data that has a well defined most-significant-bit, and
a well defined least-significant-bit can be sort in place in O(n) time.
 
: Warwick