On Friday, 15 November 2013 at 22:56:58 UTC, Craig Dillabaugh
wrote:
What are the arguments against using a randomized algorithm?
(1) Sort is capable of being marked pure, depending on the type
being sorted and the predicate. But choosing random pivots means
introducing side effects.
(2) Random pivots invoke average performance, whereas choosing
the pivot from a median of N has the potential to achieve better
performance on partially sorted lists (fewer reads and writes).
(3) I've tested random pivots and found that choosing from a
median of three or five is often the better choice.
