Heapsort, counting sort y radix sort

Hay un teorema que dice que ningún ordenamiento por comparaciones puede bajar de $n\log n$. Y hay algoritmos que ordenan en tiempo lineal. Las dos cosas son ciertas, y entender por qué no se contradicen es entender qué cuesta realmente ordenar.

Por qué comparando no se baja de n log n

Un algoritmo que sólo compara elementos de a pares puede verse como un árbol de decisión: cada comparación es una bifurcación y cada hoja, una de las $n!$ permutaciones posibles. Un árbol binario con $n!$ hojas tiene altura al menos $\log_2(n!)$, que por Stirling es $\Theta(n\log n)$.

Esa es la cota, y no depende de la astucia del algoritmo: depende de que la única operación disponible sea comparar. Los ordenamientos lineales no la violan; usan otra operación.

Heapsort: garantía de peor caso y memoria constante

Heapsort primero construye un max-heap sobre el mismo arreglo, en $O(n)$. Después, $n$ veces, intercambia la raíz con el último elemento del heap, achica el heap en uno y hace descender la nueva raíz. El elemento máximo queda en su posición final.

Es in situ y garantiza $\Theta(n\log n)$ en todos los casos, sin peor caso cuadrático ni memoria auxiliar. En la práctica corre más lento que quicksort porque salta por la memoria y desperdicia la caché. Por eso suele aparecer como red de seguridad de introsort. No es estable.

Counting sort no compara: cuenta

Counting sort no compara: cuenta. Si las claves son enteros en un rango chico $[0,k)$, arma un arreglo de $k$ contadores, cuenta cuántas veces aparece cada valor, acumula esas cuentas para saber dónde empieza cada grupo y ubica cada elemento en su posición.

El costo es $\Theta(n+k)$ y la memoria también. Con $k$ comparable a $n$ es lineal; con un rango enorme —enteros de 32 bits— es inutilizable. Recorriendo la entrada de atrás hacia adelante al ubicar, es estable, y esa estabilidad es lo que habilita el algoritmo que sigue.

Radix sort: de a un dígito, y estable

Radix sort ordena por dígitos. En su versión habitual arranca por el dígito menos significativo y aplica un ordenamiento estable —counting sort— sobre cada posición, avanzando hacia el más significativo.

La estabilidad es esencial: es lo que conserva el orden logrado por los dígitos anteriores. Con $d$ dígitos el costo es $\Theta(d\,(n+k))$; para claves de largo fijo, lineal. Sirve para enteros, fechas o cadenas de largo acotado, y necesita memoria extra.

La letra chica de los lineales

La letra chica es que estos algoritmos no ordenan cualquier cosa: necesitan claves que se puedan descomponer en dígitos o mapear a un rango. Con un comparador arbitrario definido por el usuario no hay nada que contar.

También hay que mirar las constantes: radix sort hace varias pasadas completas sobre los datos y escribe mucho. Sobre pocos elementos, quicksort le gana aunque sea asintóticamente peor.

Cuál usar en cada caso

Queda un criterio simple. Si hace falta garantía de peor caso y memoria constante, heapsort. Si las claves son enteros de rango acotado y hay memoria, counting sort. Si son enteros grandes o cadenas de largo fijo y el volumen es alto, radix sort. Para todo lo demás, un híbrido basado en comparaciones.

Cuándo se puede romper el n log n

La cota de $\Omega(n \log n)$ vale para algoritmos que sólo comparan elementos, porque cada comparación da un bit y hacen falta $\log_2(n!)$ bits para distinguir entre todas las permutaciones posibles. Los lineales no la contradicen: la esquivan, porque no comparan. Usan la clave como índice, y para eso necesitan saber algo sobre la clave de antemano.

Cierre

La cota de $n\log n$ vale para quien sólo compara. Heapsort la alcanza con garantía e in situ; counting y radix la esquivan usando la estructura de la clave, y pagan con memoria y con restricciones sobre qué se puede ordenar.