Si tengo un arreglo con pocos números pero varios repetidos, puedo hacer un

Counting Sort

Cuento cuántos repetidos de cada uno hay y los guardo en un arreglo (con tamaño k, en dónde k=max-min)

Luego, los copio en otro arreglo

Complejidad:

• temporal: O(n+k)
• Memoria: O(k)

Cuando k~n: temporal y memoria = O(n)

Por ejemplo: [1241783869]

Creo un arreglo [211101121] (tengo 2 unos, 1 dos, 1 tres…)

• Me sirve con pocos elementos y cuando conocemos el rango/imagen
• No es in-place
• Es estable

Radix sort

Hago un counting sort con el último dígito de cada número (ej, el 9 en 29), después con el anteúltimo, después con el antepenúltimo y así

Hacemos k countings

Orden:

• Temporal: O(kn)
• Memoria: O(n)

También puedo hacerlo con strings