Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!ihnp4!ptsfa!lll-lcc!styx!ames!rutgers!princeton!allegra!alice!ark
From: ark@alice.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <6671@alice.uUCp>
Date: Fri, 27-Feb-87 17:09:11 EST
Article-I.D.: alice.6671
Posted: Fri Feb 27 17:09:11 1987
Date-Received: Sun, 1-Mar-87 15:05:56 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA> <25329@rochester.ARPA>
Organization: AT&T Bell Laboratories, Liberty Corner NJ
Lines: 7
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:127 comp.lang.misc:301 comp.os.misc:42 sci.research:62

In article <25329@rochester.ARPA>, crowl@rochester.ARPA (Lawrence Crowl) writes:
> The quicksort is an inplace O(n log n) sort while the bubble sort is O(n^2).
> The quicksort will provide much better performance for the same space.  That
> is unless you are worried about program space.

But quicksort uses O(log n) additional memory, which one cannot
always afford.  It is also O(n**2) worst case.