Re:Potential Quicksort replacement in java.util.Arrays with ...
by fhars on Saturday September 12, 2009 @03:41AM
(#818739)
My copy of Knuth does only mention that algorithm with a reference to a 1970 paper.
But what I woukd find more intereting is how the parallelizable Batcher and Pratt algorithms decsribed by Knuth fare on modern multicore machines with their weird cache hierarchies.
Using more pivots is going to make the code more complicated. The benefits of moving from one pivot to two seem to be real but not enormous; I'd be pretty surprised if moving to three pivots produced benefits worth the cost. But of course that's just handwaving, and indeed it would be interesting to measure.