Counting Sort es un algoritmo de ordenamiento no por comparación que alcanza O(n + k) donde n es el tamaño del arreglo y k es el rango de valores. En lugar de comparar elementos, cuenta la frecuencia de cada valor y reconstruye el arreglo ordenado.

Es radicalmente más rápido que cualquier algoritmo de comparación (O(n log n)) cuando k es pequeño relative a n. A cambio, requiere espacio adicional proporcional al rango y solo funciona para datos enteros en un rango conocido.

Cómo Funciona

1. Cuenta: crea un arreglo count[0..k] inicializado en 0. Recorre el arreglo de entrada e incrementa count[valor].
2. Acumula: transforma count en acumulación de prefijos: count[i] += count[i-1]. Ahora count[i] es la posición final del valor i.
3. Reconstruye: recorre el arreglo de entrada de derecha a izquierda (para estabilidad). Coloca cada elemento en output[count[valor] - 1] y decrementa count[valor].
4. Copia: copia output de regreso al arreglo original.

Idea Clave

Counting Sort rompe la barrera O(n log n) porque no compara elementos. Usa el valor como índice directo en un arreglo de frecuencias. Por eso solo funciona para enteros en rango conocido.

La acumulación de prefijos (prefix sums) es lo que lo hace estable: al recorrer de derecha a izquierda, los elementos iguales se colocan en orden inverso al de aparición, preservando el orden relativo original.

Ejemplo Trabajado

Ordena [4, 2, 2, 8, 3, 3, 1] (rango k = 8):

Paso 1: Cuenta frecuencias

count: [0, 1, 2, 2, 1, 0, 0, 0, 1]
        ↑  ↑  ↑  ↑  ↑           ↑
        0  1  2  3  4           8

Paso 2: Acumula prefijos

count: [0, 1, 3, 5, 6, 6, 6, 6, 7]

Paso 3: Reconstruye (recorre derecha a izquierda):

• arr[6]=1 → output[count[1]-1=0] = 1
• arr[5]=3 → output[count[3]-1=4] = 3
• arr[4]=3 → output[count[3]-1=3] = 3
• arr[3]=8 → output[count[8]-1=6] = 8
• arr[2]=2 → output[count[2]-1=2] = 2
• arr[1]=2 → output[count[2]-1=1] = 2
• arr[0]=4 → output[count[4]-1=5] = 4

output: [1, 2, 2, 3, 3, 4, 8]

Resultado: [1, 2, 2, 3, 3, 4, 8]. Observa el visualizador mostrar el arreglo de conteo y la reconstrucción.

Casos Extremos y Trampas

• Rango grande — si k >> n, el espacio O(k) domina. No usar para rangos dispersos.
• “Valores negativos — Counting Sort estándar no maneja negativos. Solución: desplazar por el mínimo.”
• Inestable — la versión sin acumulación de prefijos pierde el orden relativo.
• No genérico — solo funciona para enteros, no strings o floats directamente.

Comparación con Radix Sort

Aplicaciones

• Counting sort como subroutine — Radix Sort para enteros de múltiples dígitos
• Histogramas — conteo de frecuencias en estadística
• Ranking — ordenar calificaciones (0-100), edades, días de la semana
• Algoritmos de texto — base de suffix array construction

Trayectoria de Práctica

1. Implementa Counting Sort estable con acumulación de prefijos; prueba en [4, 2, 2, 8, 3, 3, 1].
2. Extiende para manejar valores negativos desplazando por min(arr).
3. Analiza: ¿cuándo Counting Sort es más lento que Merge Sort? (cuando k es muy grande).
4. Usa Counting Sort como subroutine para Radix Sort de 2 dígitos en base 10.
5. Compara con Bucket Sort: ¿cuál es la diferencia fundamental?