Ordenamientos sin comparación
Gánale a O(n log n) SIN comparar: usa las llaves como índices.
Counting · radix · bucket. Lineales, con enteros acotados.
El hueco en la regla
- La cota inferior de O(n log n) solo aplica a ordenamientos por comparación
- Counting: cuenta cuántos hay de cada valor → O(n + k)
- Radix: ordena dígito por dígito (estable) → O(d·(n + b))
- Bucket: reparte por rangos, ordena cada uno → O(n) esperado
Míralo contar, no comparar
Cada elemento sube su barra. Nunca se comparan dos elementos.
Leer las barras de izquierda a derecha = ordenado.
Counting sort le gana a la librería
Counting: 3.3× más rápido que Timsort con llaves acotadas. (Radix pierde: 7 pasadas de Python.)
El detalle: el rango k
- Counting sort reserva k contadores —rango amplio = fatal
- Solo enteros (o llaves que puedas mapear a enteros)
- Bucket sort asume distribución pareja
- Datos generales → sigue siendo un ordenamiento por comparación
Para llevar
Especialistas: lineales con llaves enteras acotadas, imbatibles ahí.
El raro caso donde tu código le gana a la librería. Sigue: búsqueda — búsqueda binaria.