(Improved) Benchmark for Phobos Sort Algorithm

[Matthias Walter]

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