Сортировка слиянием
Описание
Сортировка слиянием (Merge Sort) — это эффективный стабильный алгоритм сортировки, использующий стратегию «разделяй и властвуй». Он рекурсивно разбивает массив на две половины, сортирует каждую половину, а затем сливает отсортированные половины обратно. Операция слияния — ключевая: она объединяет два отсортированных подмассива в один отсортированный массив.
Зачем это нужно
Сортировка слиянием гарантирует сложность O(n log n) в любом случае, что делает её надёжной для больших объёмов данных. Она лежит в основе многих алгоритмов внешней сортировки, используемых в базах данных и файловых системах. Понимание сортировки слиянием помогает освоить парадигму «разделяй и властвуй» и концепцию слияния отсортированных последовательностей — паттерн, используемый в merge joins, потоковой обработке и системах контроля версий.
Визуализация
Как работает алгоритм
Сортировка слиянием — классический алгоритм «разделяй и властвуй». Он работает путём рекурсивного разбиения массива на подмассивы, пока каждый не будет содержать один элемент, а затем сливает их обратно в отсортированном порядке.
1. Разделение массива
Массив разбивается на две половины в средней точке. Если массив содержит 1 или 0 элементов, он уже отсортирован — это базовый случай рекурсии.
2. Рекурсивная сортировка каждой половины
Сортировка слиянием рекурсивно применяется к левой и правой половинам. Каждый рекурсивный вызов разбивает массив дальше, пока не будут получены подмассивы размером 1.
3. Слияние двух отсортированных половин
Два отсортированных подмассива объединяются в один отсортированный массив с помощью метода двух указателей:
- Сравниваем первые элементы каждой половины. Берём меньший и сдвигаем соответствующий указатель.
- Когда одна половина исчерпана, копируем все оставшиеся элементы из другой половины.
4. Возврат результата
Слитый массив теперь полностью отсортирован. Он возвращается вверх по цепочке рекурсии. После завершения всех слияний весь массив отсортирован.
Разделение: [38, 27, 43, 3] → [38, 27] и [43, 3] → [38], [27], [43], [3] (одиночные элементы).
Слияние: [27, 38] и [3, 43] → сравниваем 27 и 3 → берём 3 → сравниваем 27 и 43 → берём 27 → ... → [3, 27, 38, 43].
Сложность
Анализ сложности
Временная сложность
O(n log n) — даже в лучшем случае сортировка слиянием выполняет все операции разделения и слияния. Количество уровней — log₂ n, на каждом уровне выполняется O(n) работы по слиянию.
O(n log n) — средний случай совпадает с лучшим и худшим. Производительность сортировки слиянием детерминирована и не зависит от распределения входных данных.
O(n log n) — в отличие от быстрой сортировки, у сортировки слиянием нет вырожденного случая. Она всегда делит массив ровно пополам и сливает за линейное время на каждом уровне.
Пространственная сложность
O(n) — сортировка слиянием требует дополнительные временные массивы для шага слияния. На каждом уровне рекурсии создаются вспомогательные массивы суммарным размером n.
Стабильная сортировка — равные элементы сохраняют относительный порядок, потому что при слиянии, когда элементы равны, сначала берётся элемент из левой половины (left[i] <= right[j]).
Быстрая сортировка имеет среднее время O(n log n), но худший случай O(n²), тогда как сортировка слиянием гарантирует O(n log n) во всех случаях. Однако сортировка слиянием использует O(n) дополнительной памяти, в то время как быстрая сортировка работает на месте с O(log n) стековой памяти. На практике быстрая сортировка часто быстрее благодаря лучшей локальности кэша.
Пример кода
function mergeSort(arr: number[]): number[] {if (arr.length <= 1) return arr;const mid = Math.floor(arr.length / 2);const left = mergeSort(arr.slice(0, mid));const right = mergeSort(arr.slice(mid));return merge(left, right);}function merge(left: number[], right: number[]): number[] {const result: number[] = [];let i = 0;let j = 0;while (i < left.length && j < right.length) {if (left[i] <= right[j]) {result.push(left[i]);i++;} else {result.push(right[j]);j++;}}// Copy remaining elementswhile (i < left.length) result.push(left[i++]);while (j < right.length) result.push(right[j++]);return result;}// Usage exampleconst unsorted = [38, 27, 43, 3, 9, 82, 10];const sorted = mergeSort(unsorted);console.log(sorted); // [3, 9, 10, 27, 38, 43, 82]
Примеры использования в реальных задачах
Внешняя сортировка в базах данных
Когда данные не помещаются в память, базы данных используют внешнюю сортировку слиянием: отсортированные серии записываются на диск, а затем сливаются за несколько проходов. Так PostgreSQL и другие СУБД сортируют большие наборы данных при ORDER BY и CREATE INDEX.
Стандартная библиотечная сортировка (стабильная)
Многие языки используют сортировку слиянием (или её вариант — Timsort) в качестве стабильного алгоритма сортировки. Python sorted(), Java Collections.sort() для объектов и стабильная сортировка Rust — все основаны на сортировке слиянием.
Merge Joins в SQL
Алгоритм merge join в базах данных SQL работает как шаг слияния сортировки слиянием: два отсортированных потока объединяются за один проход. Это одна из самых эффективных стратегий соединения, когда оба входа уже отсортированы.
Подсчёт инверсий
Классическая задача: подсчитать, сколько пар (i, j) существует, где i < j, но arr[i] > arr[j]. Сортировку слиянием можно модифицировать для подсчёта инверсий на шаге слияния за O(n log n) — используется в рекомендательных системах и измерении сходства данных.
Потоковая обработка и слияние событий
При слиянии нескольких отсортированных потоков событий (логов, временных рядов, топиков Kafka) используется шаг слияния сортировки слиянием напрямую. Этот паттерн применяется в распределённых системах, агрегации логов и базах данных временных рядов.
Системы контроля версий (3-way merge)
Git и другие системы контроля версий используют алгоритмы слияния, основанные на наибольшей общей подпоследовательности и принципах сортировки слиянием, для объединения изменений из разных веток в единый результат.