Esta es una traducción automática y la versión en inglés es la original. Leer el original
Por qué la ordenación no puede ser más rápida
Ordenar cien elementos requiere al menos 525 comparaciones. No solo con los algoritmos actuales. Nunca.
La mayoría de las afirmaciones sobre el rendimiento se refieren a un programa concreto. Esta no. Afirma que ningún algoritmo de ordenación por comparación, escrito por cualquier persona, en cualquier lenguaje o en cualquier hardware aún no inventado, puede ordenar cien elementos en menos de 525 comparaciones.
El argumento no examina en ningún momento un algoritmo.
Cuenta los destinos, no los pasos
Una lista de n elementos distintos se puede ordenar de n! formas diferentes. Solo una de ellas está ordenada y, antes de empezar, no se tiene idea de cuál se tiene entre manos.
Considera ahora lo que te aporta una comparación. Preguntas si a precede a b y obtienes un sí o un no. Un bit. Haga lo que haga tu algoritmo a continuación, lo hace sabiendo un dato binario más que antes.
Así pues, tras c comparaciones habrás recibido c bits, y c bits pueden distinguir como máximo 2c situaciones diferentes. Para tener la certeza de identificar con cuál de las n! disposiciones empezaste, necesitas
2c ≥ n!, es decir, c ≥ log₂(n!).
Esa es toda la demostración. No contiene bucles, ni recursión, ni suposiciones sobre la estrategia, razón por la cual se aplica a algoritmos en los que nadie ha pensado todavía.
El nombre habitual de este resultado es la cota del árbol de decisión. Imagina cualquier algoritmo de ordenación por comparación como un árbol: cada nodo interno es una comparación, cada rama es una de las dos respuestas y cada hoja es una disposición posible. Un árbol de profundidad c tiene como máximo 2c hojas, y el árbol debe tener al menos n! de ellas, por lo que su profundidad es de al menos log₂(n!). La profundidad es el número de comparaciones en el peor caso.
Cuáles son realmente los números
Doce elementos se pueden ordenar de 479.001.600 formas. Su logaritmo es 28,84, por lo que doce elementos necesitan al menos 29 comparaciones. Cien elementos necesitan al menos 525. Un millón necesita al menos 18.488.885.
Abre el Big-O Complexity Explorer y lee la fila correspondiente a N = 100. La columna O(N log N) indica 664, situándose entre O(N) en 100 y O(N²) en 10.000. Ese 664 es N × log₂N, el ritmo de crecimiento que consideramos óptimo para la ordenación.
Sin embargo, el límite inferior es 525, y 664 está un 26,6% por encima.
Esa diferencia no se debe a descuidadez en la herramienta. log₂(n!) no es exactamente n log₂ n: la aproximación de Stirling da n log₂ n − 1,4427n, y para N = 100 esa corrección equivale a 139 comparaciones. Así pues, «N log N» describe la forma correcta pero sobreestima el coste real en un factor constante del tamaño de entrada. La forma es lo que perdura a medida que N crece; las 139 comparaciones son lo que notarías si las contaras realmente.
La salida que no es una escapatoria
Counting sort ordenará un millón de enteros pequeños en mucho menos de 18 millones de operaciones, y no contradice ni una palabra de lo anterior.
La demostración asume que cada pregunta planteada es una comparación. Counting sort realiza un tipo de pregunta diferente: lee una clave y la utiliza como dirección. Esto extrae mucho más de un bit a la vez, porque aprovecha algo que el modelo de comparación rechaza asumir: que las claves son enteros pequeños cuyo interior se permite examinar.
Este es el hábito útil. Una cota inferior es siempre una cota inferior dentro de un modelo, y cuando parece que se ha superado un resultado, lo que ha cambiado es el modelo. Sorting Race ejecuta los algoritmos basados en comparación unos contra otros, y lo que los separa son los factores constantes y el comportamiento de la memoria, no el exponente. Todos están acotados inferiormente por los mismos 525.
Dónde has visto esto antes
Si la estrategia de contar te resulta familiar, es la misma que explica por qué ningún compresor puede comprimir todos los archivos. Allí el recuento comparaba los archivos posibles frente a los archivos más cortos posibles; aquí compara las disposiciones posibles frente a las secuencias de respuestas posibles. Ambas demostraciones funcionan al observar que un conjunto de resultados es mayor que el conjunto de elementos que podrían describirlos.
Entropy Coding aborda la misma magnitud desde la otra dirección: el número de bits que realmente necesitas viene determinado por cuántas posibilidades quedan, y ninguna codificación puede superarlo.
Ninguno de los dos resultados te dice cómo escribir un programa rápido. Te dicen cuándo dejar de buscarlo.