Tri par fusion pour les listes chaînées

Go Hard sorting

Tâche «Tri par fusion pour les listes chaînées»

Étant donné une liste simplement chaînée composée d’entiers. Il faut implémenter le tri par fusion pour cette liste. Données d’entrée : le nombre d’éléments et les éléments eux-mêmes. Données de sortie : la liste triée, affichée séparée par des espaces. Contraintes : nombre d’éléments jusqu’à 10^5, valeurs comprises entre -10^9 et 10^9. Il est requis d’utiliser l’algorithme de tri par fusion avec une complexité O(n log n) et de ne pas utiliser de tableaux supplémentaires pour stocker les valeurs.

Format d\ entrée

Première ligne : un entier n (1 ≤ n ≤ 10^5) — le nombre d’éléments. Deuxième ligne : n entiers séparés par des espaces.

Format de sortie

Une ligne : n entiers séparés par des espaces — la liste triée.

Exemples

Exemple 1

ENTRÉE

6
-5 0 10 3 -2 7

SORTIE

-5 -2 0 3 7 10

main.go