Wed, 30 Dec 2009 02:58:14 -0500, bearophile wrote: > Don: >> Yeah, that's the obvious question -- what's the optimum number of >> pivots? It's a bit annoying that that paper doesn't mention it. > > Two pivots help avoid a common bad corner case of the QuickSort (when > there are many equal items). Writing a good sorting routine is not easy, > there's lot of software engineering behind it. I have studied this topic > some.
So can you tell us then what is the optimal number of pivots? Can it be proven? They say the two-pivot version is the best improvement over the practical version of classic quicksort since sliced bread.
