Сортировка слиянием — алгоритм сортировки, который упорядочивает списки (или
другие структуры данных, доступ к элементам которых можно получать только
последовательно, например — потоки) в определённом порядке. Эта сортировка —
хороший пример использования принципа «разделяй и властвуй». Сначала задача
разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с
помощью рекурсивного вызова или непосредственно, если их размер достаточно мал.
Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
1) Сортируемый
массив разбивается на две половины примерно одинакового размера;
2) Каждая из
получившихся половин сортируется отдельно, например - тем же самым
алгоритмом;
3) Два упорядоченных массива половинного размера соединяются в
один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер
массива не достигнет единицы (любой массив длины 1 можно считать
упорядоченным).
Нетривиальным этапом является соединение двух упорядоченных массивов в один.
Основная идея заключается в следующем. Пусть мы имеем два
отсортированных по убыванию "полумассива". На каждом шаге мы берём
меньший из двух текущих элементов этих
"полумассивов" и записываем его в результирующий массив. Когда
один из оставшихся массивов становится пустым, мы добавляем все
оставшиеся элементы второго в результирующий.
