Hola.
La solución lo que hace es ir almacenando en un arreglo auxiliar llamado cantidades, la cantidad de veces que aparece cada elemento en el arreglo A (el arreglo a ordenar).
Esto lleva O(k) para inicializar cantidades y O(n) para recorrer A y contar cada elemento.
Luego, lo que hace es recorrer nuevamente A y por cada vez que aparece un elemento en cantidades lo agrega a A.
Esto es O(nk)
Veamos un ejemplo:
A = [5,1,3,2,1]
Entonces cantidades = [0,2,1,1,0,1]. Eso quiere decir que el 1 aparece 2 veces, el 2, 3 y 5 aparecen 1 vez y el 4 aparece 0 veces en A
Luego, se sobreescribe A obteniendo [1,1,2,3,4]
En cuanto a los órdenes, nos queda O(k) + O(n) + O(nk).
El mayor es O(nk) donde k es una constante que no depende de la entrada, por lo tanto es O(n).
Espero se entienda
Saludos