Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!ll-xn!cullvax!drw
From: drw@cullvax.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Information on order(N) sort
Message-ID: <849@cullvax.UUCP>
Date: Fri, 27-Feb-87 10:50:09 EST
Article-I.D.: cullvax.849
Posted: Fri Feb 27 10:50:09 1987
Date-Received: Sun, 1-Mar-87 10:22:25 EST
Organization: Cullinet Software, Inc., Westwood, MA
Lines: 16
Xref: utgpu comp.edu:122 comp.lang.misc:293 comp.os.misc:37 sci.research:57

kort@hounx.UUCP (B.KORT) writes:
> If you have memory to burn, the pigeon-hole (or post-office) sort is
> fast as lightning.  This sort doesn't even use the comparison test.

Eh?  OK, you've got zillions of bins, and putting things in them is
real fast.  Now, get them back out again, without looking at each of
the zillions of bins.  (Remember, the goal is to produce a sorted
list, not to just have fast access to the items.)  Pigeon-hole is fast
in the real world because "scan for next bin with contents" is done by
the visual hardware of the brain.

Dale
-- 
Dale Worley		Cullinet Software
UUCP: ...!seismo!harvard!mit-eddie!cullvax!drw
ARPA: cullvax!drw@eddie.mit.edu