Tri par fusion avec limitation de mémoire

Kotlin Hard sorting

Tâche «Tri par fusion avec limitation de mémoire»

Étant donné un tableau d'entiers. Il faut le trier par ordre croissant en utilisant uniquement O(1) de mémoire supplémentaire (c'est-à-dire sans utiliser de tableaux ou de listes supplémentaires). Il est permis de déplacer les éléments uniquement dans le tableau d'origine. Implémentez un algorithme de tri par fusion in-place avec une approche itérative (bottom-up). Affichez le tableau trié séparé par des espaces.

Format d\ entrée

La première ligne contient un entier N (1 ≤ N ≤ 10^5). La deuxième ligne contient N entiers séparés par des espaces.

Format de sortie

Une ligne : N entiers triés par ordre croissant, séparés par des espaces.

Exemples

Exemple 1

ENTRÉE

1
42

SORTIE

42

Exemple 2

ENTRÉE

6
6 5 4 3 2 1

SORTIE

1 2 3 4 5 6

Exemple 3

ENTRÉE

3.0 4.0

SORTIE

Invalid input

Exemple 4

ENTRÉE

6
4 2 2 8 3 3 1

SORTIE

2 2 3 3 4 8

main.kt