Randomized quick sort could pick the wrong pivot at every step (or at every other step, that's still quadratic complexity), so it's only O(n log n) with high probability.

The probability is so low that this has probably never happened in all history (for reasonably sized arrays).

It’s not typical to analyse randomised algorithms this way for that reason.

Quicksort is popular, and Quicksort bad inputs can happen in highly plausible specific cases (e.g. almost sorted input vs. pivot on first array element) and can be easily engineered whenever an attacker controls a large input to be sorted and can guess what sorting algorithm is being used. Probability of bad performance is only low on implausibly random input instances.

They are both randomized. https://en.wikipedia.org/wiki/Las_Vegas_algorithm#Relation_t...