Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!ames!ucbcad!ucbvax!sdcsvax!ucsdhub!hp-sdd!ncr-sd!ncrcae!ece-csc!uvacs!dam
From: dam@uvacs.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <1274@uvacs.CS.VIRGINIA.EDU>
Date: Mon, 2-Mar-87 16:20:25 EST
Article-I.D.: uvacs.1274
Posted: Mon Mar  2 16:20:25 1987
Date-Received: Thu, 5-Mar-87 20:45:52 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA> <25329@rochester.ARPA> <2064@cvl.umd.edu>
Reply-To: dam@uvacs.UUCP (Dave Montuori)
Organization: U.Va. CS dept.  Charlottesville, VA
Lines: 13
Xref: utgpu comp.edu:136 comp.lang.misc:317 comp.os.misc:49 sci.research:67

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....
>Also, Quicksort is O(n log n ) only in the average. The worst case is still
>O(n^2).

Quite true. I suggest using heapsort, which treats the array to be sorted
as a d-heap (d == 2 or 3 usually). It's an O(n log n) sort in both average
and worst cases, and is as much of an in-place sort as B-argh-le sort.
-- 
From the University of Virginia at Boar's Head, C.S. Department-in-Exile:
Dave Montuori (Dr. ZRFQ); DAMONT quandum, DAMONTque futurus.
dam@uvacs.cs.virginia.edu   or   {allegra | cbosgd | ncsu}!uvacs!dam
NSA line eater food: terrorist, CIA, drugs, cipher, secret, fnord, FBI, decode.