If we're being really picky it is possible to deterministically find the median of n elements in \Theta(n) time so we're able to deterministically select as our pivot the median element.

This gives deterministic \Theta(n log n).

As mentioned elsewhere this algorithm has a fairly large constant factor and is not used in practice.