Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site rtp47.UUCP Path: utzoo!linus!philabs!cmcl2!seismo!harvard!talcott!panda!genrad!decvax!mcnc!rti-sel!rtp47!throopw From: throopw@rtp47.UUCP (Wayne Throop) Newsgroups: net.math Subject: Re: Sorting a sorted list by a different order of keys Message-ID: <67@rtp47.UUCP> Date: Thu, 13-Jun-85 14:37:54 EDT Article-I.D.: rtp47.67 Posted: Thu Jun 13 14:37:54 1985 Date-Received: Tue, 18-Jun-85 02:03:31 EDT References: <7298@watdaisy.UUCP> Organization: Data General, RTP, NC Lines: 27 > In article <11259@brl-tgr.ARPA> gwyn@brl-tgr.ARPA (Doug Gwyn ) writes: > >Actually, there are some sorting methods that are better than N log N; > Pardon me? Loose lips sink ships, please define your model. > Gregory J.E. Rawlins, Department of Computer Science, U. Waterloo > {allegra|clyde|linus|inhp4|decvax}!watmath!watdaisy!gjerawlins [I take the above to mean that the second poster doubts that there are sort methods faster than NlogN, so, responding to that point:] There are indeed sorting methods that are "faster" than NlogN. Perhaps the simplest is "radix sorting", an example of which is the good old card collator (well, old anyway). The method is order N*M, where N is the number of records, and M is the "width" of the key. This method works best when keys are very narrow. In this circumstance, you can have a "bin" for each possible key value. Then the sort is order N... you simply look at the key of each record, put the record in the bin associated with it's key, and then output the contents of each bin in turn. Note that this method only outperforms a traditional quicksort or heapsort when the key is "smaller than" logN in some sense, and hence makes sense only for VERY large sets of records or VERY narrow keys. I hope this saves all those ships in danger of submersion. I'll keep my lips tight, just in case. :-) -- Wayne Throop at Data General, RTP, NC !mcnc!rti-sel!rtp47!throopw