Сортировка слиянием для связанных списков

Go Сложный sorting

Задача «Сортировка слиянием для связанных списков»

Дан односвязный список, состоящий из целых чисел. Необходимо реализовать сортировку слиянием для этого списка. Входные данные: количество элементов и сами элементы. Выходные данные: отсортированный список, выведенный через пробел. Ограничения: количество элементов до 10^5, значения в диапазоне -10^9 до 10^9. Требуется использовать алгоритм сортировки слиянием со сложностью O(n log n) и не использовать дополнительные массивы для хранения значений.

Формат ввода

Первая строка: целое число n (1 ≤ n ≤ 10^5) — количество элементов. Вторая строка: n целых чисел через пробел.

Формат вывода

Одна строка: n целых чисел через пробел — отсортированный список.

Примеры

Пример 1

ВВОД

6
-5 0 10 3 -2 7

ВЫВОД

-5 -2 0 3 7 10

main.go