From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_MSGID, URI_NOVOWEL autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,7bb5fdff3abecabe X-Google-Attributes: gid103376,public X-Google-Thread: 108717,7bb5fdff3abecabe X-Google-Attributes: gid108717,public From: mfb@mbunix.mitre.org (Michael F Brenner) Subject: Re: Algorithms: Counting- and AddressCalculation Sort Date: 1997/10/24 Message-ID: <62qfri$l6h@top.mitre.org>#1/1 X-Deja-AN: 284737173 References: <34509356.32EB39DD@biosys.net> Organization: The MITRE Corporation, Bedford Mass. Newsgroups: comp.programming,comp.lang.ada Date: 1997-10-24T00:00:00+00:00 List-Id: 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.