fastSort benchmarking (was Re: Work done so far)

[bearophile]

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

This doesn't change the fact that in many situations in your code you want to use a key() instead of a cmp().


> 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.

It beats quicksort in the common case of partially ordered input, I think. With quite varied definition of "partially". Plus other situations too, like partial reverse ordering, etc. In real world situations you usually have partially ordered data, or you have to merge two partially sorted sequences, etc. In such very common cases Timsort is probably among the best. And it's fast enough in the other cases too. You can take a look at the comparison count too.


> 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.

In my d libs there is a stable sort too. A stable sort is really useful in lot of situations, like sorting structs (multi type tuples). And Timosort was faster anyway than the not-stable sort used before it... I presume it's good mostly when you have to sort objects with a custom comparator (unlike the fastSort I have written in my D libs).


> If you find a more portable implementation

The site I have shown you has the most independent version of it you can find, I think. Jython too uses it (and I have heard that recently the Sun JavaVM may use it too, but I am not sure).

Bye,
bearophile