(Improved) Benchmark for Phobos Sort Algorithm

[Craig Black]

"Matthias Walter" <xammy at xammy.homelinux.net> wrote in message 
news:mailman.1065.1292557052.21107.digitalmars-d at puremagic.com...
> On 12/16/2010 09:36 PM, 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?
>
> Yes, there is a "flaw": There are still instances of arrays where you
> will end up with a pivot element being one of the largest or one of the
> smallest elements in *every* call. The means, that you split your array
> from length n not into two arrays roughly of size n/2 and n/2, but of
> O(1) and n - O(1). This implies a running time of n^2 (in contrast to n
> log n), which is obviously bad.
>
> I don't know how std.algorithm.sort works, but C++ STL uses an
> Introspective sort, which is a quick-sort variant like you have, but it
> has some measurements that observe whether the above worst case occurs
> (e.g. by looking at the recursion depth) and switches to a heap-sort in
> this case. [1]
>
> Matthias
>
> [1] http://en.wikipedia.org/wiki/Introsort

Thanks for the advice!  I have been looking on the internet and it seems 
introsort is the best, but I haven't found any free C/C++ code for it.

-Craig