Ordenação por mesclagem com restrição de memória

Kotlin Hard sorting

Tarefa «Ordenação por mesclagem com restrição de memória»

Dado um array de números inteiros. É necessário ordená-lo em ordem crescente, usando apenas O(1) de memória adicional (ou seja, sem usar arrays ou listas adicionais). É permitido apenas trocar elementos no array original. Implemente um algoritmo de ordenação por mesclagem in-place com abordagem iterativa (bottom-up). Imprima o array ordenado separado por espaços.

Formato de Entrada

A primeira linha contém um número inteiro N (1 ≤ N ≤ 10^5). A segunda linha contém N números inteiros, separados por espaços.

Formato de Saída

Uma única linha: N números inteiros, ordenados em ordem crescente, separados por espaços.

Exemplos

Exemplo 1

ENTRADA

1
42

SAÍDA

42

Exemplo 2

ENTRADA

6
6 5 4 3 2 1

SAÍDA

1 2 3 4 5 6

Exemplo 3

ENTRADA

3.0 4.0

SAÍDA

Invalid input

Exemplo 4

ENTRADA

6
4 2 2 8 3 3 1

SAÍDA

2 2 3 3 4 8

main.kt