"in" everywhere

[Sean Kelly]

Peter Alexander Wrote:

> On 9/10/10 4:53 PM, bearophile wrote:
> > Andrei:
> >
> >> Currently std.algorithm.getPivot picks the middle of the range as the
> >> pivot, but I made it modular such that it can be improved in a number of
> >> ways (i.e. randomized, median-of-3, median-of-5, etc).
> >
> > Isn't median of 3 a better default?
> >
> > Bye,
> > bearophile
> 
> There is no "best". They are all trade-offs between the time taken to 
> select the pivot and the suitability of the pivot.
> 
> Middle - Fastest, not very good
> Median-of-3 - Slower, but slightly better
> Median-of-5 - Slower still, but even better
> 
> Randomized - Speed depends on the random number algorithm. Suitability 
> is random, so could be good, could be bad, but on average it's good 
> enough. Has the added quality that it's practically impossible to devise 
> worst-case input for it (you'd need to know the generator and seed), 
> whereas for the other 3, a malicious user could provide data that gives 
> you O(n^2) complexity.

Introsort (a quicksort variant) degrades to heapsort for sorts that are going quadratic (it tracks the recursion depth and transitions when the depth is more than a desired threshold for the size of the range).  The sort routine I wrote for Tango uses this approach plus media-of-3, the insertion sort fallback, and the quicksort variant that separately tracks equal values.  All told, it's as fast or faster than everything else I've tested, even for contrived degenerate cases.  Perhaps I'll convert it to use ranges and see how it does.