Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!ihnp4!ptsfa!lll-lcc!seismo!mimsy!cvl!bhaskar
From: bhaskar@cvl.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <2064@cvl.umd.edu>
Date: Thu, 26-Feb-87 21:46:21 EST
Article-I.D.: cvl.2064
Posted: Thu Feb 26 21:46:21 1987
Date-Received: Sun, 1-Mar-87 08:37:43 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA> <25329@rochester.ARPA>
Organization: Center for Automation Research, Univ. of Md.
Lines: 13
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:120 comp.lang.misc:291 comp.os.misc:35 sci.research:55
Summary: Space complexity of Quicksort

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).