fastSort benchmarking (was Re: Work done so far)

[Matti Niemenmaa]

bearophile wrote:
> Notes:
> - Two or more sorts can be kept, one for native data, one for more complex
> sorting, etc. (That's what I do in my d libs)

True.

> - Some of the situations where you use cmp() can be managed with a string
> mixin, maybe this can speed things up some.

Also true, this is what Andrei does in 2.0's std.algorithm, as torhu said. And 
it probably does speed things up.

> - A better support of inlining by DMD may change the situation some.

In some cases, yes, but in this general case of passing a function pointer I 
don't think it can help.

> - In many simple situations where speed and data size are less important a
> key() function is simpler to use than cmp(). See sorted/sortedAA in d libs.
> If uou use a key() you often don't need a cmp() too.

If speed is less important you probably don't care that much about the algorithm 
  being used either. ;-)

> - Try adapting Timsort used by Python, probably it's not easy to find
> something better: http://py-stablesort.sourceforge.net/

I haven't tested timsort but I gather its main selling point is that it's 
stable. As such I don't think it'll be faster than an average quicksort 
(although I could be completely wrong, of course), since, as far as I can tell, 
it's a highly optimized version of merge sort.

As the docs say: "an adaptive, stable, natural mergesort, modestly called
timsort". The situations in which one needs a stable sort are, IMHO, rare enough 
that it should be considered a special case and thereby a separate function/method.

I'm willing to concede without evidence that timsort is among the fastest stable 
sorts, but I'll admit I'd be a bit surprised if even a hand-optimized C 
implementation working on arrays would beat stdlib's qsort() or your algorithm, 
for instance.

I can't test it since the original code uses the Python API instead of sorting a 
void* or the like. If you find a more portable implementation or feel like 
porting it yourself, feel free to benchmark it and see how it performs.

-- 
E-mail address: matti.niemenmaa+news, domain is iki (DOT) fi