🚀 go-pugleaf

In article <11008@uqcspe.cs.uq.oz.au> warwick@cs.uq.oz.au writes:
)foo@netcom.com (Mark Hall) writes: (about radix sort)
)>   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?

   Not really. If you had such a hashing function, it seems you could
sort N arbitrary size integers in O(N) time. 

   You propose a O(1) hash that takes N arbitrary integers of P bits 
each, mapping them to integers of log N bits *preserving the 
order of the original numbers* ? The order is what you are 
trying to find in the first place! 

   If you can find such a hash function, just use it to map the 
original numbers to integers from 1 to N, then print the original
numbers corresponding to 1, 2, 3 etc.  You are done. No need to 
radix sort at that point. 

   I suspect that your O(1) hash function doesn't exist.

   - mark