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

Сортировка слиянием (англ. merge sort) — это алгоритм сортировки, основанный на принципе «разделяй и властвуй». Он относится к классу алгоритмов сортировки на основе сравнений и гарантирует время выполнения O(n log n) в худшем, среднем и лучшем случаях. Сортировка слиянием является устойчивой (stable), то есть не меняет порядок равных элементов, и часто используется для сортировки больших объёмов данных, особенно когда требуется стабильность и предсказуемая производительность.

История

Идея сортировки слиянием была впервые предложена американским математиком и пионером компьютерной науки Джоном фон Нейманом в 1945 году. Он разработал этот алгоритм для использования на ранних электронно-вычислительных машинах. В 1948 году фон Нейман опубликовал детальное описание метода в своей работе «Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components». Алгоритм оставался важным теоретическим открытием, но не получил широкого практического применения до 1960-х годов, когда развитие компьютерных систем потребовало эффективных методов обработки больших массивов данных (например, на магнитных лентах). В 1961 году, в связи с ростом популярности программирования, слиянием заинтересовались практики: в СССР этот метод был описан в учебнике А. А. Боровкова «Элементы математической статистики» (1962) и активно применялся в вычислительной технике того времени.

Принцип работы

Сортировка слиянием реализует стратегию «разделяй и властвуй» в три этапа:

1. Разделение (Divide): Исходный массив неупорядоченных элементов рекурсивно делится пополам до тех пор, пока не будут получены подмассивы, состоящие из одного элемента. Одноэлементный массив считается отсортированным по определению.
2. Завоевание (Conquer): Каждый такой подмассив снова объединяется (сливается) с соседним подмассивом. При слиянии элементы из двух соседних подмассивов упорядоченно сравниваются и помещаются в результирующий подмассив.
3. Объединение (Combine): Процесс повторяется рекурсивно или итеративно до тех пор, пока не будет получен один отсортированный массив размером, равным исходному.

Ключевой операцией является слияние двух отсортированных массивов. Эта операция выполняется за время O(n), где n — общее количество элементов в сливаемых подмассивах. В процессе слияния требуется дополнительная память для временного хранения результата.

Пример работы на массиве [38, 27, 43, 3, 9, 82, 10]

1. Разделение:

• [38, 27, 43, 3] и [9, 82, 10]
• [38, 27] и [43, 3]; [9, 82] и [10]
• [38] и [27]; [43] и [3]; [9] и [82]; [10]

1. Слияние:

• [27, 38] и [3, 43]; [9, 82] и [10]
• [3, 27, 38, 43] и [9, 10, 82]
• [3, 9, 10, 27, 38, 43, 82]

Реализация

Существуют две основные реализации сортировки слиянием: рекурсивная (сверху вниз) и итеративная (снизу вверх).

Рекурсивная сортировка слиянием (top-down)

Это классический способ, непосредственно следующий из описания. Алгоритм вызывает сам себя для левой и правой половин массива, а затем сливает их. Код на псевдоязыке:

`` function mergeSort(array): if length(array) <= 1: return array middle = length(array) / 2 left = mergeSort(array[0:middle]) right = mergeSort(array[middle:length(array)]) return merge(left, right) ``

Итеративная сортировка слиянием (bottom-up)

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

`` function mergeSortIterative(array): n = length(array) size = 1 while size < n: for i from 0 to n - 1 step 2 size: left = array[i:i+size] right = array[i+size:i+2size] array[i:i+2size] = merge(left, right) size = size 2 ``

Классификация и варианты

Сортировка слиянием с внешней памятью (External merge sort)

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

Естественная сортировка слиянием (Natural merge sort)

Этот вариант оптимизирует процесс за счёт выявления уже отсортированных участков (ранов) в исходном массиве. Вместо того чтобы делить массив пополам, алгоритм сразу ищет упорядоченные последовательности. Это позволяет сократить количество операций при работе с частично отсортированными данными.

Сортировка слиянием без дополнительной памяти (In-place merge sort)

Существуют попытки реализовать слияние без использования дополнительной O(n) памяти, но все такие алгоритмы имеют существенные недостатки (сложность реализации, нестабильность, замедление производительности). Классический in-place алгоритм (например, метод Олсона) увеличивает время до O(n log² n) или требует перестановок, нарушающих устойчивость. На практике in-place версии используются редко.

Характеристики

Сложность по времени

• Худший случай: O(n log n)
• Средний случай: O(n log n)
• Лучший случай: O(n log n)

Сложность по памяти

• Обычная версия: O(n) дополнительной памяти (для хранения копий массивов при слиянии).
• Итеративная (реализация с указателями): O(n) или O(1) в зависимости от конкретной реализации (при работе с массивами обычно O(n)).
• In-place версии: O(log n) для стека вызовов, или O(1) — но с увеличением времени.

Устойчивость (стабильность)

Сортировка слиянием является устойчивой (stable) по умолчанию. При равенстве ключей порядок элементов в исходной последовательности сохраняется, если алгоритм слияния реализован корректно (элементы из левого подмассива помещаются в результат перед равными элементами из правого).

Производительность на практике

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

Применение

Сортировка слиянием применяется в различных областях:

• Системы управления базами данных (СУБД): Для сортировки больших таблиц, которые не помещаются в оперативную память, используется внешняя сортировка слиянием.
• Операционные системы: В файловых системах и при сортировке каталогов (например, в Linux-утилите sort по умолчанию используется внешняя сортировка слиянием).
• Сортировка связанных списков: Сортировка слиянием особенно эффективна для односвязных и двусвязных списков, так как не требует произвольного доступа к памяти. Рекурсивный подход работает за O(n log n) и легко реализуется.
• Библиотеки языков программирования: В Python стандартная функция sorted() и метод list.sort() используют Timsort — гибридный алгоритм, который сочетает сортировку вставками и слиянием. В Java стандартный Collections.sort() (для объектов) также основан на Timsort. В C++ std::stable_sort часто реализован через сортировку слиянием.
• Параллельные алгоритмы: Сортировка слиянием хорошо параллелится: разделение массива может выполняться независимо на разных процессорах, а слияние — в несколько потоков.

Критика

Основные недостатки сортировки слиянием связаны с использованием дополнительной памяти. Классическая рекурсивная версия требует O(n) дополнительного пространства, что делает её неэффективной для очень больших массивов, где оперативная память ограничена. Кроме того, рекурсивная реализация может привести к переполнению стека вызовов (stack overflow) при глубине рекурсии ~log₂ n, что для массивов из 2²⁰ элементов (около миллиона) составляет 20 вызовов — проблема возникает редко, но на встраиваемых системах с маленьким стеком она реальна.

Также сортировка слиянием не является адаптивной: она всегда выполняет O(n log n) операций, даже если массив уже отсортирован. В таких случаях алгоритмы вроде Timsort или сортировки вставками могут работать за O(n).

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (CLRS), 4-е издание, 2022.
• Кнут Д. Э. «Искусство программирования. Том 3. Сортировка и поиск», 2-е издание, 1998.
• Седжвик Р., Уэйн К. «Алгоритмы на Java», 4-е издание, 2015.
• Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. «Introduction to Algorithms», 4th ed., 2022.