Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: Eric Sosman <esosman@ieee-dot-org.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: Verifying a list is alphabetized
Date: Sun, 04 Dec 2011 08:47:42 -0500
Organization: A noiseless patient Spider
Lines: 17
Message-ID: <jbftm4$e3f$1@dont-email.me>
References: <722147ec-ab43-4d7c-8b41-32f8705ee7db@i8g2000vbh.googlegroups.com> <jb5k7n$g4u$1@dont-email.me> <4ed9732b$0$294$14726298@news.sunsite.dk> <jbd5k5$86c$1@dont-email.me> <b5sld7ltif6oi2tke3q2fkr5vnr2cc6nkc@4ax.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 4 Dec 2011 13:47:48 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="HSlJAUb3pGXi3i7ZL/HoAw"; logging-data="14447"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+FVrXayNf3ur8Zxd+npQXG"
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:8.0) Gecko/20111105 Thunderbird/8.0
In-Reply-To: <b5sld7ltif6oi2tke3q2fkr5vnr2cc6nkc@4ax.com>
Cancel-Lock: sha1:cU60k5Vb/q+6wrTaFEaS3biT+7k=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:10487

On 12/3/2011 11:05 PM, Roedy Green wrote:
> On Sat, 03 Dec 2011 07:44:48 -0500, Eric Sosman
> <esosman@ieee-dot-org.invalid>  wrote, quoted or indirectly quoted
> someone who said :
>
>>      What is the big-Oh complexity of Collections.sort(List<String>)
>> on an already-sorted list?
>
> IIRC QuickSort goes a bit bananas if the file is already sorted. [...]

     Since Collections.sort() does not use Quicksort (in fact, it
promises *not* to use Quicksort!), observations on Quicksort's
behavior, however interesting, do not bear on the issue at hand.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid