Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Joshua Cranmer Newsgroups: comp.lang.java.programmer Subject: Re: Did the sort do anything? Date: Thu, 12 May 2011 10:40:57 -0400 Organization: A noiseless patient Spider Lines: 20 Message-ID: References: <9303hcFq0nU1@mid.individual.net> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Thu, 12 May 2011 14:40:57 +0000 (UTC) Injection-Info: mx01.eternal-september.org; posting-host="3xSaU6y5tAyBQEIxw+DaTw"; logging-data="15911"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19eDJVBQuCFulUShOaVcPfnj3EhE3XMXio=" User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.16pre) Gecko/20110305 Lightning/1.0b3pre Thunderbird/3.1.10pre In-Reply-To: <9303hcFq0nU1@mid.individual.net> Cancel-Lock: sha1:1oHUrGnrFtBlHNQJ8Nmm31l1fiM= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:4012 On 05/11/2011 02:40 PM, Robert Klemme wrote: > Btw, couldn't option 3 be tricky? Depending on the sorting algorithm > things might be moved around but the final order might be the same as > before. Not that this would be desirable but I am pretty sure there are > sorting algorithms which have this property (probably quicksort). The term you are looking for is the stability of the sort. A stable sort preserves the order of equally-compared object; unstable sorts do not. Of the major sorts, heapsort and quicksort are the only sorts which are unstable, although a bad of implementation of any stable sort could be unstable. Wikipedia claims that quicksort can be implemented stably, but that comes at an O(n) space price. Java uses quicksort for primitive types in Arrays.sort and mergesort for reference types: since you can't distinguish two equal primitive types, you can't tell that quicksort isn't stable. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth