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.
