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

Гоша: Значит, алгоритмом быстрой сортировки можно отсортировать данные за $O(n \log n)$. Но в худшем случае метод работает за $O(n^2)$. Есть ли алгоритмы, которые и в худшем случае имеют сложность $O(n \log n)$?

Тимофей: Да, есть.

Гоша: И почему тогда алгоритм быстрой сортировки назвали так?

Гоша: Это всё замечательно. Но хотелось бы найти решение, которое всегда работает за $O(n \log n)$.

Тимофей: Сейчас я расскажу про алгоритм сортировки, который работает за $O(n \log n)$ даже в худшем случае.

Алгоритм сортировки слиянием (англ. merge sort) чаще всего реализуется с использованием принципа «разделяй и властвуй».

Задачу разбивают на подзадачи меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал, то есть, когда дошли до базового случая рекурсии. Решения подзадач комбинируют и получают решение исходной задачи.

Алгоритм сортировки слиянием работает так:

Условие остановки рекурсии — массив из одного элемента. Это базовый случай. Такой массив не нуждается в сортировке.

Как соединить два упорядоченных массива в один?

Например, даны два подмассива, отсортированные по возрастанию.

На каждом шаге из двух первых подмассивов берём меньший элемент и записываем его в результирующий массив. Счётчики подмассива, из которого взят элемент, и результирующего массива увеличиваем на 1.

Когда один из подмассивов закончился, добавляем оставшиеся элементы второго подмассива в результирующий массив.

В лучшем случае алгоритму слияния двух отсортированных массивов, имеющих длины $n$ и $m$, потребуется $min(n, m)$ операций сравнения. В худшем: $n + m - 1.$ Лучшие алгоритмы сортировки это учитывают в своей работе.

Рассмотрим пример работы алгоритма сортировки слиянием:

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