Mergesort für verknüpfte Listen

Go Hard sorting

Aufgabe «Mergesort für verknüpfte Listen»

Gegeben ist eine einfach verknüpfte Liste, die aus ganzen Zahlen besteht. Es soll ein Mergesort für diese Liste implementiert werden. Eingabedaten: die Anzahl der Elemente und die Elemente selbst. Ausgabedaten: die sortierte Liste, durch Leerzeichen getrennt ausgegeben. Einschränkungen: Anzahl der Elemente bis zu 10^5, Werte im Bereich von -10^9 bis 10^9. Es ist der Mergesort-Algorithmus mit einer Komplexität von O(n log n) zu verwenden und es dürfen keine zusätzlichen Arrays zum Speichern der Werte verwendet werden.

Eingabeformat

Erste Zeile: eine ganze Zahl n (1 ≤ n ≤ 10^5) — die Anzahl der Elemente. Zweite Zeile: n ganze Zahlen, durch Leerzeichen getrennt.

Ausgabeformat

Eine Zeile: n ganze Zahlen, durch Leerzeichen getrennt — die sortierte Liste.

Beispiele

Beispiel 1

EINGABE

6
-5 0 10 3 -2 7

AUSGABE

-5 -2 0 3 7 10

main.go