Re: Algorithms: Counting- and AddressCalculation Sort

[mfb@mbunix.mitre.org (Michael F Brenner)]

According to the ieee dictionary at the url: 
http://stdsbbs.ieee.org/groups/610/formata.html
an address calculation sort is an insertion sort
where the items get put into lists based on their
addresses and then those lists are merged. That makes
it sound like a hashcode is computed and the hashcode
is used to determine approximately where to put the
item (that is, plus or minus one list). A large enough
hashcode, combined with a widely enough distributed
statistical distribution of the data, and sufficient
RAM (double the key space) results in a very efficient
sort. If any of these three is missing, it wont work.
If you actually use addresses instead of hash codes, 
then double the key space is insufficient. You must
have a perfect hashcode address function to linearize
the sorting time. Also you must take into account that
if you have an imperfect address computation or hashcode,
then those lists will have more than one member and 
storage space must be made for those lists as well as
for links between those lists, and time for maintaining,
allocating, and deallocating those lists and their
members.

According to the URL http://ww.cs.cmu.edu/~scandal/nesl/algorithsm.html
a counting sort computes the number of keys less than each of the
keys. This does not seem to be a fast way to sort. It also seems
that after you have made all of your counts, you must still
sort those counts.