Clasificación por conteo con restauración del orden

Java Hard sorting

Tarea «Clasificación por conteo con restauración del orden»

Dado un arreglo de números enteros. Es necesario ordenarlo de forma ascendente utilizando el algoritmo de clasificación por conteo (counting sort). Sin embargo, cuando los valores de los elementos son iguales, se debe conservar su orden relativo original (ordenamiento estable). Genere el arreglo ordenado. Restricciones: longitud del arreglo de 1 a 10^5, valores de los elementos de -10^4 a 10^4.

Formato de entrada

La primera línea contiene un número entero N (1 ≤ N ≤ 100000) — la cantidad de elementos. La segunda línea contiene N números enteros separados por espacios — los elementos del arreglo.

Formato de salida

Genere N números — el arreglo ordenado, separados por espacios.

Ejemplos

Ejemplo 1

ENTRADA

5
3 1 2 1 3

SALIDA

1 1 2 3 3

Ejemplo 2

ENTRADA

4
-2 0 -2 1

SALIDA

-2 -2 0 1

Ejemplo 3

ENTRADA

1
42

SALIDA

42

main.java