(Improved) Benchmark for Phobos Sort Algorithm

[Andrei Alexandrescu]

On 12/16/10 9:05 PM, Russel Winder 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.

Yeah, when reading this I was like, "the last sentence ain't likely to 
be as well received as others". :o) All - let's take it easy.

I implemented std.algorithm sort and it reuses partition(), another 
algorithm, and uses Singleton's partition of first, middle, last 
element. I also eliminated a few obvious risks of quadratic behavior. 
See comment on line 3831:

http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/algorithm.d?rev=1279#L3808

I was familiar at the time with Bentley's paper but there is only so 
much time to spend on implementing one algorithm when I had fifty others 
on my plate. I think std.algorithm.sort does an adequate job but it can 
be improved in many ways.


Andrei