Ordenamiento por mezcla con limitación de memoria

Kotlin Hard sorting

Tarea «Ordenamiento por mezcla con limitación de memoria»

Dado un arreglo de números enteros. Es necesario ordenarlo de forma ascendente, utilizando solo O(1) de memoria adicional (es decir, sin usar arreglos o listas adicionales). Solo se permite intercambiar elementos dentro del arreglo original. Implemente un algoritmo de ordenamiento por mezcla in-place con enfoque iterativo (bottom-up). Imprima el arreglo ordenado separado por espacios.

Formato de entrada

La primera línea contiene un número entero N (1 ≤ N ≤ 10^5). La segunda línea contiene N números enteros separados por espacios.

Formato de salida

Una línea: N números enteros ordenados de forma ascendente, separados por espacios.

Ejemplos

Ejemplo 1

ENTRADA

1
42

SALIDA

42

Ejemplo 2

ENTRADA

6
6 5 4 3 2 1

SALIDA

1 2 3 4 5 6

Ejemplo 3

ENTRADA

3.0 4.0

SALIDA

Invalid input

Ejemplo 4

ENTRADA

6
4 2 2 8 3 3 1

SALIDA

2 2 3 3 4 8

main.kt