Time and Space Complexity

Complejidad Temporal:

• O(n + k)
  • donde n es el número de elementos y k es el rango de valores (max + 1). Una pasada para contar, una pasada sobre los conteos para reconstruir.
• Cuando k es pequeño y fijo, esto es efectivamente O(n), más rápido que el O(n log n) de los ordenamientos por comparación.

Complejidad Espacial:

• O(n + k)
  • El arreglo de conteo usa O(k) y la salida usa O(n).

Resumen:

• Counting Sort es un ordenamiento estable, no basado en comparaciones, que se ejecuta en tiempo lineal para rangos pequeños de enteros.
• No es adecuado cuando el rango de valores k es muy grande, porque el arreglo de conteo sería enorme. Esta versión asume enteros no negativos.