Сортировка слиянием (Merge Sort): принцип работы, сложность и эффективность

Сортировка слиянием (Merge Sort) – один из классических алгоритмов «разделяй и властвуй». Она широко используется в учебных курсах и практических задачах благодаря предсказуемой сложности и простоте реализации. Ниже подробно рассмотрим принцип работы, оценку сложности, причины эффективности и примеры реализации на популярных языках программирования.

Основная идея алгоритма

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

1. Разделение – исходный массив рекурсивно делится пополам, пока не получим подмассивы длиной 1 (они уже отсортированы по определению).
2. Слияние (merge) – отсортированные подмассивы последовательно объединяются в один отсортированный массив.

Таким образом, сортировка строится снизу вверх: сначала сортируются минимальные части, затем они «склеиваются» в всё более крупные отсортированные блоки.

Пошаговый процесс

Разделение массива

Для массива A[0 … n‑1] находим средний индекс mid = n/2 и рекурсивно вызываем сортировку для левой (A[0 … mid‑1]) и правой (A[mid … n‑1]) частей.

Слияние двух отсортированных подмассивов

Предположим, у нас есть два уже отсортированных массива L и R. Создаём результирующий массив result и два указателя i и j, początkowo равные 0. Затем:

• Сравниваем L[i] и R[j];
• Меньший элемент копируем в result и сдвигаем соответствующий указатель;
• Повторяем, пока один из массивов не закончится;
• Оставшиеся элементы второго массива просто дописываем в конец result.

Полученный result – отсортированный массив, содержащий все элементы L и R.

Сборка результата

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

Оценка сложности

Временная сложность

На каждом уровне рекурсии мы выполняем слияние всех n элементов – это O(n) операций. Количество уровней рекурсии равно количеству раз, которое можно делить пополам массив, пока не дойдём до единицы: log₂ n. Следовательно, общая сложность:

T(n) = O(n)·O(log n) = O(n log n).

Эта оценка справедлива для лучшего, среднего и худшего случая, потому что деление всегда происходит пополам, а процесс слияния линейно зависит от размера подмассивов.

Пространственная сложность

Для слияния требуется дополнительный массив размером n (или два временных массива по n/2 каждый). Поэтому дополнительная память – O(n). Рекурсивный стек потребляет O(log n) места, но он не доминирует.

Почему Merge Sort считается эффективным?

• Предсказуемая производительность – гарантированная O(n log n) во всех случаях, unlike quicksort, который может деградировать до O(n²) при неудачном выборе опорного элемента.
• Устойчивость (stability) – равные элементы сохраняют свой исходный порядок, что важно при сортировке сложных записей по нескольким полям.
• Параллелизм – этапы разделения и слияния легко распараллеливаются: разные части массива можно сортировать независимо на разных ядрах или потоках.
• Эффективность для внешней сортировки – когда данные находятся на медленных носителях (диски, ленты) и доступ возможен только последовательно, Merge Sort минимизирует количество проходов, так как каждое слияние работает с уже отсортированными блоками.
• Простота доказательства корректности – рекуррентное соотношение T(n) = 2·T(n/2) + O(n) легко решается мастер‑теоремой, что упрощает академический анализ.

Сравнение с другими популярными сортировками

Как видно, Merge Sort сочетает гарантированную логарифмическую линейную сложность с устойчивостью, хотя и требует дополнительной памяти.

Пример реализации

На Python

def merge_sort(arr):
 if len(arr) <= 1:
 return arr
 mid = len(arr) // 2
 left = merge_sort(arr[:mid])
 right = merge_sort(arr[mid:])
 return merge(left, right)

def merge(left, right):
 result = []
 i = j = 0
 while i < len(left) and j < len(right):
 if left[i] <= right[j]:
 result.append(left[i])
 i += 1
 else:
 result.append(right[j])
 j += 1
 result.extend(left[i:])
 result.extend(right[j:])
 return result

На C++

void merge(vector& a, int l, int m, int r) {
 int n1 = m — l + 1, n2 = r, m;
 vector L(n1), R(n2);
 for (int i = 0; i < n1; ++i) L[i] = a[l + i];
 for (int j = 0; j < n2; ++j) R[j] = a[m + 1 + j];
 int i = 0, j = 0, k = l;
 while (i < n1 && j < n2) {
 if (L[i] <= R[j]) a[k++] = L[i++];
 else a[k++] = R[j++];
 }
 while (i < n1) a[k++] = L[i++];
 while (j < n2) a[k++] = R[j++];
}

void mergeSort(vector& a, int l, int r) {
 if (l >= r) return;
 int m = l + (r, l) / 2;
 mergeSort(a, l, m);
 mergeSort(a, m + 1, r);
 merge(a, l, m, r);
}

На Java

public static void mergeSort(int[] arr, int left, int right) {
 if (left >= right) return;
 int mid = left + (right ⎯ left) / 2;
 mergeSort(arr, left, mid);
 mergeSort(arr, mid + 1, right);
 merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
 int n1 = mid ⎯ left + 1;
 int n2 = right — mid;
 int[] L = new int[n1];
 int[] R = new int[n2];
 System.arraycopy(arr, left, L, 0, n1);
 System.arraycopy(arr, mid + 1, R, 0, n2);
 int i = 0, j = 0, k = left;
 while (i < n1 && j < n2) {
 if (L[i] <= R[j]) arr[k++] = L[i++];
 else arr[k++] = R[j++];
 }
 while (i < n1) arr[k++] = L[i++];

 while (j < n2) arr[k++] = R[j++];
}

Преимущества и недостатки

Преимущества

• Гарантированная O(n log n) сложность.
• Устойчивая сортировка.
• Хорошо подходит для внешней сортировки и работы с последовательными структурами данных (списки, файлы).
• Легко параллелизируется.

Недостатки

• Требует дополнительной памяти O(n) (не «in‑place»).
• Рекурсивная реализация может вызывать переполнение стека при очень больших n (можно заменить итеративным bottom‑up вариантом).
• На небольших массивах постоянные факторы делают её медленнее, чем простые алгоритмы вроде вставки; поэтому часто используют гибридные подходы (например, Timsort).

Когда стоит использовать Merge Sort?

• Когда необходима гарантированная производительность независимо от входных данных.
• Когда важна устойчивость сортировки (например, при сортировке записей по нескольким полям).
• При работе с внешними носителями, где доступ к данным последователен.
• В многопоточных или распределённых системах, где этапы разделения можно выполнять параллельно.

Merge Sort – это надёжный, предсказуемый и устойчивый алгоритм сортировки, который находит применение как в учебных целях, так и в реальных системах, требующих стабильной производительности. Несмотря на необходимость дополнительной памяти, его преимущества в виде гарантированной O(n log n) сложности, устойчивости и хорошей параллелизуемости делают его одним из столпов современной алгоритмической библиотеки.