Go rant

[Don]

bearophile wrote:
> retard:
>> So can you tell us then what is the optimal number of pivots?<
> 
> I can tell you that two pivot, used in the correct way, lead to a good quicksort, as I've said.
> 
> 
>> Can it be proven?
> 
> I don't know. It can be proven that two pivot are enough to avoid the problem with the classic QuickSort.
> 
> Bye,
> bearophile

 From a cursory glance, it seems that the number of swaps (0.8) 
ultimately comes out of the binomial theorem, so it ought to be 
straightforward to expand the analysis.

I also suspect that it'd be better to switch from two-pivot to one-pivot 
quicksort at some value of n.
It'd be interesting to know how the two-pivot quicksort compares to timsort.

I suspect there's a median-of-five-killer worst case for this quicksort, 
just as there's a median-of-three killer for standard quicksort.