Сортировка слиянием — это эффективный алгоритм сортировки, работающий по принципу «разделяй и властвуй». Он обладает стабильностью и гарантированной сложностью O(n log n).
📌 Алгоритм сортировки слиянием
- Разделение массива на две половины
- Рекурсивная сортировка каждой половины
- Слияние отсортированных половин
💻 Реализация на PHP
<?php
function mergeSort(array $arr): array {
if (count($arr) <= 1) {
return $arr;
}
$middle = (int)(count($arr) / 2);
$left = mergeSort(array_slice($arr, 0, $middle));
$right = mergeSort(array_slice($arr, $middle));
return merge($left, $right);
}
function merge(array $left, array $right): array {
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] < $right[$j]) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}
// Пример использования
$array = [38, 27, 43, 3, 9, 82, 10];
$sorted = mergeSort($array);
print_r($sorted);
?>🌐 Реализация на JavaScript
1. Классическая версия
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const middle = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, middle));
const right = mergeSort(arr.slice(middle));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
// Пример использования
const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(array));2. Версия с визуализацией шагов
function mergeSortWithSteps(arr, level = 0) {
console.log(`${' '.repeat(level)}Сортируем:`, arr);
if (arr.length <= 1) {
console.log(`${' '.repeat(level)}Базовый случай:`, arr);
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = mergeSortWithSteps(arr.slice(0, middle), level + 1);
const right = mergeSortWithSteps(arr.slice(middle), level + 1);
const merged = merge(left, right);
console.log(`${' '.repeat(level)}Сливаем ${left} и ${right} →`, merged);
return merged;
}
const nums = [5, 2, 4, 7, 1];
console.log("Исходный массив:", nums);
console.log("Результат:", mergeSortWithSteps(nums));⚡ Сравнение с другими алгоритмами
| Характеристика | Merge Sort | Quick Sort | Bubble Sort |
| Сложность (средняя) | O(n log n) | O(n log n) | O(n²) |
| Сложность (худшая) | O(n log n) | O(n²) | O(n²) |
| Память | O(n) | O(log n) | O(1) |
| Стабильность | Да | Нет | Да |
📌 Когда использовать?
- Плюсы Merge Sort:
- Гарантированная сложность O(n log n)
- Стабильность (сохраняет порядок равных элементов)
- Хорош для связных списков и внешней сортировки
- Минусы:
- Требует дополнительной памяти O(n)
- Медленнее Quick Sort на небольших массивах
Оптимальное применение: большие массивы (от 10k элементов), где важна стабильность.
Другие виды сортировок
- Quick Sort — быстрая сортировка
- Bubble Sort — сортировка пузырьком