Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.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: Sat, 03 Dec 2011 07:44:48 -0500
Organization: A noiseless patient Spider
Lines: 30
Message-ID: <jbd5k5$86c$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>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 3 Dec 2011 12:44:53 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="HSlJAUb3pGXi3i7ZL/HoAw"; logging-data="8396"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19zdy9kozcAaTd4EpOawJIX"
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:8.0) Gecko/20111105 Thunderbird/8.0
In-Reply-To: <4ed9732b$0$294$14726298@news.sunsite.dk>
Cancel-Lock: sha1:mpDbjYlT4SF6kF3mccNZKETE9jg=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:10465

On 12/2/2011 7:54 PM, Arne Vajhøj wrote:
> On 11/30/2011 11:05 AM, Knute Johnson wrote:
>> On 11/30/2011 7:52 AM, laredotornado wrote:
>>> I'm using Java 1.6. Given a java.util.List of Strings, what is the
>>> quickest way to verify that the list is sorted in ascending order?
>>>
>>> Thanks, - Dave
>>
>> If it could possibly unsorted, I'd just sort it. How big is this list
>> anyway?
>
> If it is small it does not matter.
>
> But I would not recommend an O(nlogn) solution for a O(n)
> problem unless there is a note in 72 pt red blinking
> on top of it.

     What is the big-Oh complexity of Collections.sort(List<String>)
on an already-sorted list?

     (Note that Oracle -- unwisely, IMHO -- specifies the sorting
algorithm as part of the method's contract, although "a modified
mergesort..." leaves a lot of wiggle room.  But anyhow: at least
one interpretation of "a modified mergesort" would be a natural
merge, which would use N-1 comparisons to discover that the input
consisted of just one run and would then leave that run alone.)

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