Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watrose!jsgray
From: jsgray@watrose.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort (new quicksort result requires no extra space)
Message-ID: <8515@watrose.UUCP>
Date: Sat, 28-Feb-87 13:30:22 EST
Article-I.D.: watrose.8515
Posted: Sat Feb 28 13:30:22 1987
Date-Received: Sun, 1-Mar-87 13:26:13 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA> <25329@rochester.ARPA> <2064@cvl.umd.edu>
Reply-To: jsgray@watrose.UUCP (Jan Gray)
Organization: U. of Waterloo, Ontario
Lines: 15
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:123 comp.lang.misc:297 comp.os.misc:38 sci.research:58

In article <2064@cvl.umd.edu> bhaskar@cvl.umd.edu (S.K. Bhaskar) writes:
>
>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.

There is a new result from Europe which shows it is possible to
quicksort with no extra space!  (And *you* thought you knew all there
was to know about quicksort, didn't you!  (I did)).  The key idea is to
mark the subfiles to be sorted by slightly changing the order of already
sorted subfiles.

I'll post more detailed information and the reference soon.

Jan Gray    jsgray@watrose    University of Waterloo    (519) 885-1211 x3870