Что такое «Сортировка слиянием»
Алгоритм приписывают Джону фон Нейману, описавшему его в 1945 году. Он построен по принципу «разделяй и властвуй»: большую задачу сводят к маленьким, решают их и собирают ответ. Массив из одного элемента уже отсортирован — это базовый случай. Всё остальное делается слиянием.
Слияние — ключевая операция. Есть две отсортированные половины. Сравниваются их первые элементы, меньший уходит в результат, указатель в его половине сдвигается. Так повторяется, пока одна половина не закончится, а остаток второй дописывается в конец.
Реализация на PHP
function mergeSort(array $a): array
{
$n = count($a);
if ($n <= 1) return $a;
$l = mergeSort(array_slice($a, 0, intdiv($n, 2)));
$r = mergeSort(array_slice($a, intdiv($n, 2)));
$res = []; $i = $j = 0;
while ($i < count($l) && $j < count($r)) {
$res[] = $l[$i] <= $r[$j] ? $l[$i++] : $r[$j++];
}
return array_merge($res, array_slice($l, $i), array_slice($r, $j));
}
Для [5, 2, 4, 1] функция разделит массив на [5, 2] и [4, 1], затем на отдельные числа, сольёт их в [2, 5] и [1, 4] и в итоге в [1, 2, 4, 5]. Сама функция вызывает себя, то есть использует рекурсию.
Сильные и слабые стороны
- Время работы пропорционально n·log n в любом случае, даже на неудачных данных. У быстрой сортировки худший случай хуже.
- Сортировка устойчива: равные элементы сохраняют исходный порядок. Это важно при сортировке товаров сначала по цене, потом по наличию.
- Нужна дополнительная память, сравнимая с размером массива.
Где её используют на практике
На практике сортировку слиянием редко пишут вручную: в языках есть встроенные функции. Но идея слияния живёт внутри них. Алгоритм Timsort, который сочетает слияние с сортировкой вставками, используется в Python и для сортировки объектов в Java. Базы данных применяют внешнюю сортировку слиянием, когда данные не помещаются в память: сортируют куски, сохраняют на диск и сливают. В PHP начиная с версии 8.0 встроенные функции сортировки тоже устойчивы.
Связанные термины
Обновлено: 10 октября 2026

