Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: Cindy Newsgroups: comp.lang.java.programmer Subject: Re: Did the sort do anything? Date: Mon, 07 Nov 2011 22:22:19 -0500 Organization: UWA OKB Lines: 15 Message-ID: References: <4d8fb7l8qb1g820cphr4fh447a9uitlddj@4ax.com> NNTP-Posting-Host: PeK9C/JchrWuRhsTrIEaEA.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: tin/1.6.2-20030910 ("Pabbay") (UNIX) (CYGWIN_NT-6.0/1.5.22(0.156/4/2) (i686)) Hamster/2.0.2.2 X-Notice: Filtered by postfilter v. 0.8.2 Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:9770 On 07/11/2011 10:02 PM, Cindy wrote: > On 07/11/2011 3:50 PM, Dagon wrote: >> Note that #1 is a different question than you asked. "would a sort >> change the order" is not the same as "did a sort change the order". > > Isn't the simplest method (assuming a stable sort algorithm is/would be > used) just to grovel over the input checking that thing[n] < thing[n+1] > and returning true immediately if not, and false if the end of the input > is reached? I.e., "is it already sorted?" seems equivalent to "would a > sort change the order?" when the sort would be a stable sort. Clarification: "equivalent" in the sense that knowing the answer to either immediately tells you the answer to the other. However, the answers, of course, have opposite signs here so you'd have to negate one to get the other.