Pattern-defeating quicksort
[Post-edit] I made several edits to the post below. First, to make   an argument. Second, to add paragraphs. [&#x2F;Post-edit]<p>Tl;dr version: It seems to me you should either use heapsort or plain quicksort; the latter with the sort of optimisations described in the linked article, but not including the fallback to heapsort.<p>Long version:<p>Here&#x27;s my reasoning for the above:<p>You&#x27;re either working with lists that are reasonably likely to trigger the worst case of randomised quicksort, or you&#x27;re not working with such lists. By likely, I mean the probability is not extremely small.<p>Consider the case when the worst case is very unlikely: you&#x27;re so unlikely to have a worst case that you&#x27;re gaining almost nothing for accounting for it except extra complexity. So you might as well only use quicksort with optimisations that are likely to actually help.<p>Next is the case that a worst case might actually happen. Again, this is not by chance; it has to be because someone can predict your &quot;random&quot; pivot and screw with your algorithm; in that case, I propose just using heapsort. Why? This might be long, so I apologise. It&#x27;s because usually when you design something, you design it to a high tolerance; a high tolerance in this case ought to be the worst case of your sorting algorithm. In which case, when designing and testing your system, you&#x27;ll have to do extra work to tease out the worst case. To avoid doing that, you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort.