Path: csiph.com!x330-a1.tempe.blueboxinc.net!aioe.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: markspace <-@.> Newsgroups: comp.lang.java.programmer Subject: Re: Did the sort do anything? Date: Tue, 10 May 2011 08:48:18 -0700 Organization: A noiseless patient Spider Lines: 23 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Tue, 10 May 2011 15:48:23 +0000 (UTC) Injection-Info: mx01.eternal-september.org; posting-host="FaSG3tOezrXhBMTb3srAdg"; logging-data="19591"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19emxHVlCORba59+tzlookKEG5WA0+ozoU=" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.2.17) Gecko/20110414 Thunderbird/3.1.10 In-Reply-To: Cancel-Lock: sha1:eDY7Dzb+bvQIuZHH/7wAkerFsoU= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:3917 On 5/10/2011 8:06 AM, Roedy Green wrote: > Often you sort things when they are already sorted. > > I am interested in simple algorithms to detect whether the sort > actually did anything. > > Some suggestions: > > 1. do a pairwise compare of the times before the sort, and if all is > in order, bypass the sort. This one here is probably the best idea of those you list. Note that you'll save a bit of time avoiding sorts with the current merge sort that Java uses, but a Tim sort (soon to be the standard sort in Java) does this already, so in the long run you'll just add an O(n) to your sorts. If possible, you should get on the Java developer list (it requires a full release though) and make some suggestions. Returning a boolean for "I did something" is not a terrible idea. I also see occasionally people ask for a way to keep to disparate lists in sync when sorting. This might be useful too. I.e., provide a way to override the "swap" function in the sort.