Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!brl-adm!brl-sem!ron
From: ron@brl-sem.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <649@brl-sem.ARPA>
Date: Wed, 25-Feb-87 17:31:45 EST
Article-I.D.: brl-sem.649
Posted: Wed Feb 25 17:31:45 1987
Date-Received: Fri, 27-Feb-87 22:45:46 EST
References: <814@fmsrl7.UUCP>
Distribution: world
Organization: Electronic Brain Research Lab
Lines: 10
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:113 comp.lang.misc:282 comp.os.misc:29 sci.research:51


The O(nlog n) lower bound is for sorts in place.
RADIX sorts can easily be done in lower time.
Think of an old model 82 sorter (for those of you who have
been around long enough).  It has lots of little bins (memory
locations) to place the output data.  The runtime is
O(Number of Cards * Number of columns in the data).
Usually the number of cards >> the sort key size.

-Ron