Сортировка слиянием с ограничением по памяти

Kotlin Сложный sorting

Задача «Сортировка слиянием с ограничением по памяти»

Дан массив целых чисел. Необходимо отсортировать его по возрастанию, используя только O(1) дополнительной памяти (т.е. без использования дополнительных массивов или списков). Разрешается переставлять элементы только в исходном массиве. Реализуйте алгоритм сортировки слиянием in-place с итеративным подходом (bottom-up). Выведите отсортированный массив через пробел.

Формат ввода

Первая строка содержит целое число N (1 ≤ N ≤ 10^5). Вторая строка содержит N целых чисел, разделённых пробелами.

Формат вывода

Одна строка: N целых чисел, отсортированных по возрастанию, разделённых пробелами.

Примеры

Пример 1

ВВОД

1
42

ВЫВОД

42

Пример 2

ВВОД

6
6 5 4 3 2 1

ВЫВОД

1 2 3 4 5 6

Пример 3

ВВОД

3.0 4.0

ВЫВОД

Invalid input

Пример 4

ВВОД

6
4 2 2 8 3 3 1

ВЫВОД

2 2 3 3 4 8

main.kt