Tri par comptage avec préservation de l'ordre

Java Hard sorting

Tâche «Tri par comptage avec préservation de l'ordre»

Soit un tableau d'entiers. Il faut le trier par ordre croissant en utilisant l'algorithme de tri par comptage (counting sort). Cependant, pour des éléments de même valeur, il faut conserver leur ordre relatif initial (tri stable). Affichez le tableau trié. Contraintes : longueur du tableau de 1 à 10^5, valeurs des éléments de -10^4 à 10^4.

Format d\ entrée

La première ligne contient un entier N (1 ≤ N ≤ 100000) — le nombre d'éléments. La deuxième ligne contient N entiers séparés par des espaces — les éléments du tableau.

Format de sortie

Affichez N nombres — le tableau trié, séparés par des espaces.

Exemples

Exemple 1

ENTRÉE

5
3 1 2 1 3

SORTIE

1 1 2 3 3

Exemple 2

ENTRÉE

4
-2 0 -2 1

SORTIE

-2 -2 0 1

Exemple 3

ENTRÉE

1
42

SORTIE

42

main.java