🚀 go-pugleaf

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.

>)>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 !!!!!!

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

See?

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.

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