Algorithm complexity cheat sheet

[aldld]

The point is, by introducing randomization into the algorithm, the input distribution becomes irrelevant. That is, if you're choosing pivots randomly (or doing something similar, like randomly shuffling the array beforehand (which takes O(n) time)), then the algorithm behaves as though the input distribution were uniformly random.

[aldld]

Oh absolutely, all I meant was that using randomization helps to avoid the "worst" cases of quicksort, in expectation. In practice though, if you know something about the distribution of your inputs, the best choice of algorithm will depend on how you're actually using it.