Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!ihnp4!houxm!hounx!kort
From: kort@hounx.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <1080@hounx.UUCP>
Date: Thu, 26-Feb-87 13:58:52 EST
Article-I.D.: hounx.1080
Posted: Thu Feb 26 13:58:52 1987
Date-Received: Sat, 28-Feb-87 05:36:26 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA> <561@aw.sei.cmu.edu.sei.cmu.edu>
Distribution: world
Organization: AT&T Bell Laboratories, Holmdel
Lines: 10
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:117 comp.lang.misc:284 comp.os.misc:32 sci.research:52
Summary: The slowest sort is the bubble sort. The fastest sort is the pigeonhole sort.

If you're short on memory, the bubble sort, slow and humble as it is,
will get the job done.  It uses lots of pair-wise comparisons.

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.

Space and time are often interchangeable.  As memory becomes cheaper,
space-intensive applications become more attractive.

Barry Kort