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

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.