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!ucbcad!ucbvax!decvax!tektronix!reed!psu-cs!omepd!uoregon!markv
From: markv@uoregon.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <456@uoregon.UUCP>
Date: Sat, 28-Feb-87 00:59:54 EST
Article-I.D.: uoregon.456
Posted: Sat Feb 28 00:59:54 1987
Date-Received: Sun, 1-Mar-87 16:39:16 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA> <25329@rochester.ARPA> <2064@cvl.umd.edu>
Reply-To: markv@drizzle.UUCP (Mark VandeWettering)
Organization: University of Oregon, Computer Science, Eugene OR
Lines: 34
Xref: utgpu comp.edu:128 comp.lang.misc:304 comp.os.misc:43 sci.research:63

In article <2064@cvl.umd.edu> bhaskar@cvl.umd.edu (S.K. Bhaskar) writes:
>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.
>
>Quicksort requires atleast O(log n) space ; Bubblesort is an in-place sort.
>The extra space needed by Quicksort is the space used by the data structure
>which maintains the subfiles still to be sorted.
>
>Also, Quicksort is O(n log n ) only in the average. The worst case is still
>O(n^2).

First of all, O(log n) space is really not than much space, according to
my handy dandy calculater...
	log(1000000) is only 13.  

Figure roughly four bytes of storage necessary for each recursive call
(lower+upper bound, shorts) We have roughly 26 bytes of storage.  Not
really too bad...

Also, the worst case performance isn't too bad, particularly if you are
reasonably clever about picking pivots.   

I have always been partial to an in-situ heap sort, but only because it
reminds me of myself cleaning my apartment... :-)

Keep the faith.  

-- 
Mark VandeWettering
University of Oregon Computer and Information Sciences Department
markv@uoregon.edu OR markv@uoregon.uucp