Смысл сортировки слиянием

В основе сортировки слиянием лежит принцип "Разделяй и властвуй":

• Разделение: Сортируемые элементы разбиваются на две группы, каждая из меньших групп сортируется рекурсивно(делится на меньшие, пока не получится один элемент в группе, а он считается отсортированным).
• Слияние: Две отсортированные группы сливаются воедино. Их первые элементы сравниваются между собой, и нужный элемент(обычно меньший) записывается в итоговый массив. Этот процесс повторяется, пока все элементы не объединятся.

Графическая иллюстрация работы сортировки слиянием

Процесс слияния описание алгоритма

Эффективность данной сортировки напрямую зависит от эффективности слияния отсортированных частей. Поэтому делается это следующим образом :

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

Оценка сложности алгоритма сортировки слиянием

Разделение: сложность $O(\log n)$, так как массив(список) делится на части пока не получатся части единичной длины. Высота такого дерева: $O(\log_2 n)$ . Это хорошо видно на рисунке.

Слияние: сложность $O(n)$. Процесс слияния двух частей занимает линейное время, пропорциональное общему количеству элементов на текущем уровне, то есть $O(n)$.

Итог: Умножаем количество уровней рекурсии на сложность на каждом из них, получаем общую сложность $O(n \log n)$.

Пример кода сортировки слиянием

void merge_sort(item_type s[], int low, int high) {
    int middle = (low + high) / 2;
    if (low < high) {
        merge_sort(s, low, middle);
        merge_sort(s, middle + 1, high);
        merge(s, low, middle, high);// функция слияния двух массивов
    }
}

Литература

[ Скиена 2022 с. 159]