Ordenação por mesclagem para listas encadeadas

Go Hard sorting

Tarefa «Ordenação por mesclagem para listas encadeadas»

Dada uma lista simplesmente encadeada composta por números inteiros. É necessário implementar a ordenação por mesclagem para esta lista. Dados de entrada: quantidade de elementos e os próprios elementos. Dados de saída: lista ordenada, exibida separada por espaços. Restrições: quantidade de elementos até 10^5, valores no intervalo de -10^9 a 10^9. É necessário usar o algoritmo de ordenação por mesclagem com complexidade O(n log n) e não utilizar arrays adicionais para armazenar os valores.

Formato de Entrada

Primeira linha: um número inteiro n (1 ≤ n ≤ 10^5) — a quantidade de elementos. Segunda linha: n números inteiros separados por espaços.

Formato de Saída

Uma linha: n números inteiros separados por espaços — a lista ordenada.

Exemplos

Exemplo 1

ENTRADA

6
-5 0 10 3 -2 7

SAÍDA

-5 -2 0 3 7 10

main.go