Что такое сортировка слиянием?

Сортировка слиянием (Merge Sort) — это алгоритм сортировки, основанный на принципе "разделяй и властвуй". Он рекурсивно разбивает массив на меньшие подмассивы до тех пор, пока не останутся подмассивы из одного элемента (которые считаются отсортированными). Затем он постепенно сливает эти отсортированные подмассивы, создавая отсортированный массив большего размера.

Алгоритм состоит из двух основных этапов:

1. Разделение: Массив рекурсивно делится пополам до тех пор, пока каждый подмассив не будет содержать только один элемент.
2. Слияние: Отсортированные подмассивы сливаются попарно, создавая новые отсортированные подмассивы большего размера. Этот процесс продолжается до тех пор, пока все подмассивы не будут объединены в один отсортированный массив.

Функция слияния принимает два отсортированных подмассива и объединяет их в один отсортированный массив. Это делается путем сравнения первых элементов каждого подмассива и добавления наименьшего из них в результирующий массив, пока оба подмассива не станут пустыми.

Сортировка слиянием является стабильной (сохраняет относительный порядок равных элементов) и имеет гарантированное время выполнения О(n log n) как в худшем, та