(Improved) Benchmark for Phobos Sort Algorithm

[spir]

On Fri, 17 Dec 2010 03:05:02 +0000
Russel Winder <russel at russel.org.uk> wrote:

> On Thu, 2010-12-16 at 20:36 -0600, Craig Black wrote:
> > It was brought to my attention that the quick sort has a very bad worst 
> > case, so I implemented a simple fix for it.  Now the worst case (completely 
> > ordered) is the best case, and it only slows down the general case by a 
> > small percentage.  I thought to myself, "it can't be this easy to fix quick 
> > sort".  Does anyone see a flaw in this simple fix?  Performs much better 
> > than Phobos in completely random and completely sorted data.  Perhaps there 
> > is another case where it doesn't do as well?
> 
> Is there any reason to not just follow Bentley and McIlroy,
> ``Engineering a Sort Function,'' SP&E 23(11), p.1249-1265, November
> 1993.  It is what the Java folk and the Go folk do for sorting arrays
> (and slices in Go).  The Java folk use a modified Merge Sort for sorting
> collections.   It's all to do with stability as well as algorithmic
> complexity.
> 
> Quicksort and Merge Sort is, however, a research industry so it will
> undoubtedly be the case that there is significantly more work done in
> the last 17 years.  This is especially true for parallel sorting.  A
> library for D undoubtedly needs both a sequential and a parallel sort
> function.  The Go folk haven't tackled this yet, and I can#t see the C++
> and Java folk tackling it for the forseeable future even though it is
> basically a necessity.
> 
> I have no doubt that people on this list could easily contribute to the
> research activity in this area, and perhaps that is what some would like
> to do, but to tinker away at algorithms outside the context of all the
> research work done on this seems like the fastest way to be treated as
> amateur hackers.
> 

What about TimSort? http://en.wikipedia.org/wiki/Timsort
(Was also considered to replace QuickSort in Lua.)

Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com