1. ¿Cómo funciona el Radix Sort?

Existen dos variantes principales:

• LSD (Least Significant Digit): procesa los dígitos desde el menos significativo al más significativo. Es la variante más usada para enteros y strings.
• MSD (Most Significant Digit): procesa los dígitos desde el más significativo, útil cuando la longitud de los elementos varía.

En ambas variantes se emplea un algoritmo estable (usualmente Counting Sort) como sub‑rutina para clasificar cada posición de dígito.

Complejidad

• Tiempo: O(k·(n+b)) donde k es el número de dígitos, n la cantidad de elementos y b la base (radix).
• Espacio: O(n+b) (auxiliar para el conteo).

2. Implementación en Python (LSD)

def counting_sort_by_digit(arr, exp, base=10):
    """Ordena ``arr`` según el dígito representado por ``exp`` (10^i)."""
    n = len(arr)
    output = [0] * n
    count = [0] * base
    # Conteo de ocurrencias del dígito actual
    for num in arr:
        index = (num // exp) % base
        count[index] += 1
    # Transformar count en posiciones acumulativas
    for i in range(1, base):
        count[i] += count[i - 1]
    # Construir el arreglo de salida (recorriendo al revés para estabilidad)
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % base
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    return output
def radix_sort(arr, base=10):
    """Radix Sort (LSD) para una lista de enteros no negativos.
    Si necesitas ordenar números negativos, revisa la sección "Manejo de negativos".
    """
    if not arr:
        return []
    # Encuentra el número máximo para saber cuántos dígitos procesar
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        arr = counting_sort_by_digit(arr, exp, base)
        exp *= base
    return arr
# Ejemplo rápido
if __name__ == "__main__":
    data = [170, 45, 75, 90, 802, 24, 2, 66]
    print("Original:", data)
    print("Ordenado:", radix_sort(data))

El algoritmo es estable: el orden relativo de elementos con el mismo dígito se mantiene, lo que lo hace ideal para ordenaciones por múltiples claves.

3. Ejemplo paso a paso (base 10)

Con la lista [170, 45, 75, 90, 802, 24, 2, 66]:

1. Exp = 1 (unidades): se ordena por el último dígito → [170, 90, 802, 2, 24, 45, 75, 66]
2. Exp = 10 (decenas): se ordena por el segundo dígito → [802, 2, 24, 45, 66, 170, 75, 90]
3. Exp = 100 (centenas): se ordena por el tercer dígito → [2, 24, 45, 66, 75, 90, 170, 802]

Después del tercer paso, la lista está completamente ordenada.

4. Comparativa con otros algoritmos de ordenación

5. Optimizaciones avanzadas

Manejo de números negativos

Separa los valores positivos y negativos, aplica Radix Sort a cada subconjunto y concatena negatives[::-1] + positives.

Base personalizada

Usar una base mayor (p. ej., 256) reduce el número de pasadas, pero aumenta el coste de la fase de conteo. En Python, base=256 funciona bien con bytes o numpy.uint8.

Paralelismo con multiprocessing

from multiprocessing import Pool
def parallel_radix_sort(arr, base=256):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        # Dividir el arreglo en chunks y ordenar cada chunk en paralelo
        chunks = [arr[i:i+len(arr)//4] for i in range(0, len(arr), len(arr)//4)]
        with Pool() as p:
            sorted_chunks = p.starmap(counting_sort_by_digit, [(c, exp, base) for c in chunks])
        # Fusionar los chunks (merge simple por estabilidad)
        arr = [item for sublist in sorted_chunks for item in sublist]
        exp *= base
    return arr

Esta variante escala bien en máquinas con varios núcleos y es útil para datasets de varios millones de registros.

6. Troubleshooting y buenas prácticas

• Datos no enteros: Convierte a entero (p. ej., usando ord() para caracteres) o utiliza Radix Sort para strings con base 256.
• Base demasiado grande: Puede provocar MemoryError por la lista count. Mantén base ≤ 2^16 en la mayoría de los entornos.
• Rendimiento inesperado: Verifica que el algoritmo de conteo sea estable y que no haya conversiones innecesarias dentro del bucle principal.

7. Preguntas frecuentes (FAQ)

¿Radix Sort es siempre más rápido que QuickSort?

No. Solo cuando k y b son pequeños respecto a n. En datos aleatorios de gran rango, QuickSort suele ser más rápido.

¿Puede usarse con tipos flotantes?

Sí, pero requiere normalizar la representación (por ejemplo, convertir a entero usando la mantisa y exponente) o usar una variante de Radix Sort para números de punto flotante que preserve el orden de signo.

¿Qué tan estable es con strings de longitud variable?

La variante MSD es la recomendada; procesa del carácter más significativo y recurre a Radix Sort recursivamente en buckets.

8. Conclusión

El Radix Sort es una herramienta poderosa en el arsenal del desarrollador cuando se trabaja con datos de dominio restringido (IDs, códigos, fechas). Su complejidad lineal bajo condiciones adecuadas lo convierte en una alternativa competitiva frente a algoritmos basados en comparaciones. Sin embargo, es esencial evaluar el rango de los datos, la disponibilidad de memoria y la necesidad de estabilidad antes de adoptarlo.

Experimenta con diferentes bases, combina con numpy para vectores masivos y aprovecha el paralelismo para obtener el máximo rendimiento.