[ruggeri]

Even without randomization of pivots expected run time is O(n log n). If the order of the input data is random, I don't believe randomizing pivots changes the distribution of running times.

What changes is that one very common permutation of data (ascending data) does not have O(n * 2) performance.

[brudgers]

There's little justification for expecting data to behave randomly unless our algorithm introduces it.

[mtdewcmu]

Correct. In general, real data will seldom, if ever, look like random data.