Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!selfless.tophat.at!news.glorb.com!npeer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!spln!extra.newsguy.com!newsp.newsguy.com!news5 From: Michael Wojcik Newsgroups: comp.lang.java.programmer Subject: Re: Did the sort do anything? Date: Wed, 18 May 2011 11:14:21 -0400 Organization: Micro Focus Lines: 37 Message-ID: References: NNTP-Posting-Host: pa0daf8d9fb4332173293b9f4b67a7fe5a445e1906323c9d9.newsdawg.com Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.8.1.23) Gecko/20090812 Thunderbird/2.0.0.23 Mnenhy/0.7.5.0 In-Reply-To: Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:4257 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? The usual problem with heapsort-based algorithms, besides having O(n lg n) as a lower bound, is that they have lousy locality of reference. In traditional heapsort, once the heap is built, you proceed by taking the leftmost element in the array (the root of the heap) and swapping it with the last element of the heap part of the array. If the heap size is not trivial, you're doing a load from one cache line and a store into another. Smoothsort appears to fix this problem, because it keeps the largest elements at the right end of the forest of heaps, so the move from the forest of heaps to the sorted part of the array is local. It also avoids having to re-heapify large heaps, since it always operates on the smallest heap left in the forest, and it splits large heaps as it dequeues from them. In fact, while I've never tried implementing smoothsort, much less analyzed its behavior, it looks like it has quite good locality of reference. But Timsort has great locality of reference, because it deals in runs (including reversed-order runs), and when it doesn't have a decent run at the current position, it sorts a small fragment of the array to create one. On the other hand, when sorts are used in most modern applications, they're comparing keys that are located elsewhere in memory and probably invoking a user-supplied comparison function, so locality of reference may not have much effect on performance. -- Michael Wojcik Micro Focus Rhetoric & Writing, Michigan State University