Worst-case performance of quickSort / getPivot

[Xinok]

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.