Mergesort mit Speicherbegrenzung

Kotlin Hard sorting

Aufgabe «Mergesort mit Speicherbegrenzung»

Gegeben ist ein Array aus ganzen Zahlen. Es muss aufsteigend sortiert werden, wobei nur O(1) zusätzlicher Speicher verwendet werden darf (d.h. ohne Verwendung zusätzlicher Arrays oder Listen). Es ist erlaubt, Elemente nur im ursprünglichen Array zu verschieben. Implementieren Sie den in-place Mergesort-Algorithmus mit einem iterativen Ansatz (bottom-up). Geben Sie das sortierte Array, getrennt durch Leerzeichen, aus.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl N (1 ≤ N ≤ 10^5). Die zweite Zeile enthält N ganze Zahlen, getrennt durch Leerzeichen.

Ausgabeformat

Eine Zeile: N ganze Zahlen, aufsteigend sortiert, getrennt durch Leerzeichen.

Beispiele

Beispiel 1

EINGABE

1
42

AUSGABE

42

Beispiel 2

EINGABE

6
6 5 4 3 2 1

AUSGABE

1 2 3 4 5 6

Beispiel 3

EINGABE

3.0 4.0

AUSGABE

Invalid input

Beispiel 4

EINGABE

6
4 2 2 8 3 3 1

AUSGABE

2 2 3 3 4 8

main.kt