Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site u1100s.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!spuxll!abnji!u1100a!u1100s!sjs
From: sjs@u1100s.UUCP (Stan Switzer)
Newsgroups: net.math
Subject: Re: Sorting a sorted list by a different order of keys
Message-ID: <204@u1100s.UUCP>
Date: Fri, 14-Jun-85 11:37:41 EDT
Article-I.D.: u1100s.204
Posted: Fri Jun 14 11:37:41 1985
Date-Received: Sat, 15-Jun-85 09:59:22 EDT
References: <7298@watdaisy.UUCP> <67@rtp47.UUCP>
Reply-To: sjs@u1100s.UUCP (Stan Switzer)
Organization: Bell Communications Research, Piscataway, NJ
Lines: 42
Summary: 

In article <67@rtp47.UUCP> throopw@rtp47.UUCP (Wayne Throop) writes:
> > In article <11259@brl-tgr.ARPA> gwyn@brl-tgr.ARPA (Doug Gwyn <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
> 
>    [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.

BUT, unless there is heavy duplication of keys, the width if the key is
at least LOG(base radix) number of records.  So the radix sort is at least
N log N under normal circumstances.

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

As I said above, this requires a heavy duplication of 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
> <the-known-world>!mcnc!rti-sel!rtp47!throopw

Well you might!

P.S.  Special cases can almost always be exploited: partial sortedness,
      updates to sorted files, sparse, dense, uniform distributions, etc.

------------------------------------------------------------------------------
Stan Switzer     |  "You know, they're growing mechanical trees / They grow to
ihnp4!u1100s!sjs |   their full height and chop themselves down" - L. Anderson