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: Sun, 15 May 2011 04:56:20 -0700 Organization: A noiseless patient Spider Lines: 16 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Sun, 15 May 2011 11:56:26 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="Gyo0FQiuGFjMddvl0JJHxw"; logging-data="28299"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18r+/J6EhkcW979Weq8c3WoPx/LWANMJhQ=" 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:z2zrlh32MxfYkZCIVy4bVCiXU0Q= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:4111 On 5/15/2011 3:20 AM, Tom Anderson wrote: > What would shut me up would be a performance comparison of two > comparable-quality implementations of the algorithms, showing that > Timsort wipes the floor with Smoothsort. Is anyone aware of one? I'm not sure, but I believe the advantage of Timsort over Smoothsort is that Timsort has O(n) performance for both ascending and descending sequences, where Smoothsort appears to only have O(n) for ascending sequences. There was a recent "shoot out" among various sort algorithms, and Timsort won. I don't recall exactly which algorithms were included, but I'm sure if Smoothsort were a serious contender it would have been examined.