Сортировка слиянием. Сложность алгоритма

Гоша: Классный алгоритм! Значит, он работает за $O(n \log n)$ даже в худшем случае?

Тимофей: Да, разберёмся почему.

На каждом шаге разбиваем массив на две примерно равные по размеру части.

Разбиение продолжается до тех пор, пока длина массива не станет равной 1.

Всего потребуется $\log_2 n$ разбиений.

На каждом шаге нужно выполнить операцию слияния двух отсортированных массивов.

Для этого потребуется $O(n)$ операций, ведь на каждом уровне рекурсии нужно обработать $n$ чисел.

Таким образом, общая сложность $O(n \log n)$.

Гоша: Классно! Кажется, мы нашли самое быстрое решение для обеих задач Кондратия. С помощью этого алгоритма мы сможем упорядочить города в соответствии со значением «треш-индекса» и оптимизировать алгоритм выявления нарушителей.

Тимофей: Ну, не скажу, что это решение самое быстрое. К тому же, алгоритму требуется $O(n)$ дополнительной памяти.

Гоша: Разве можно отсортировать данные быстрее?

Тимофей: Скоро узнаешь!

Решите задачи H и I: https://contest.yandex.ru/contest/18899/problems/