losMedian of medians El enfoque es muy popular enquicksort escriba algoritmos de partición para obtener un pivote bastante bueno, de manera que particione la matriz de manera uniforme. Su lógica se da en Wikipedia como:

El pivote elegido es menor que y mayor que la mitad de los elementos en la lista de medianas, que está alrededor de n / 10 elementos (1/2 * (n / 5)) para cada mitad. Cada uno de estos elementos es una mediana de 5, lo que hace que sean menos que otros 2 elementos y más que otros 2 elementos fuera del bloque. Por lo tanto, el pivote tiene menos de 3 (n / 10) elementos fuera del bloque y es mayor que otros 3 (n / 10) elementos fuera del bloque. De este modo, la mediana elegida divide los elementos entre 30% / 70% y 70% / 30%, lo que asegura el comportamiento lineal del algoritmo en el peor de los casos.

¿Alguien me lo puede explicar un poco lúcidamente? Me está resultando difícil entender la lógica.