It is possible to find the median in linear time (quickselect). Pivoting on the median makes quicksort optimal (O(n log(n))) while only using constant space.

It is possible to find the median in linear time (quickselect). Pivoting on the median makes quicksort optimal (O(n log(n))) while only using constant space. This is rarely used in practice because the overhead is large compared to the probability of being given a worst-case problem.