Existe un algoritmo de coste asintótico lineal, en el caso peor, para el problema de selección, es decir, para el cálculo del k-ésimo menor elemento (o estadístico de orden k) de un vector de tamaño n. Por tanto, en particular, puede usarse para el cálculo de la mediana (haciendo k = techo(n/2) ).

Os lo incluyo debajo, extraído del libro Introducion to Algorithms, de Cormen, Leiserson, Rivest y Stein.

Una vez se dispone de un algoritmo de coste lineal (caso peor) para el cálculo de la mediana, existe una modificación del algoritmo quicksort que tiene coste O(n logn) en el caso peor. Consiste en elegir la mediana como el pivote que se utiliza para la partición del vector en dos trozos, en cada llamada recursiva del quicksort.