Merge Sort (Сортировка слиянием)
Краткое описание
Рекурсивный алгоритм «разделяй и властвуй», который делит массив пополам до тех пор, пока не останутся массивы из 1 элемента, а затем сливает отсортированные части в один отсортированный массив. Гарантирует O(n log n) во всех случаях, но требует O(n) дополнительной памяти.
Когда использовать
- Гарантированная производительность критична — O(n log n) в любом случае (лучший, средний, худший), в отличие от Quick Sort с его O(n²) худшим случаем
- Стабильная сортировка обязательна — сохраняет относительный порядок равных элементов, что важно при многоуровневой сортировке
- Большие наборы данных — эффективнее простых алгоритмов O(n²) для больших массивов
- Внешняя сортировка — идеальна для сортировки файлов на диске или данных, не помещающихся в память
- Связные списки (linked lists) — работает с последовательным доступом без необходимости индексации
- Данные с похожими значениями — в отличие от Quick Sort, не деградирует до O(n²) на одинаковых элементах
- Параллелизация — легко распараллеливается, так как независимые подзадачи можно выполнять одновременно
Когда не стоит использовать:
- Ограничения по памяти — требует O(n) дополнительной памяти, что может быть критично
- Малые массивы — накладные расходы на рекурсию и создание временных массивов делают его медленнее простых алгоритмов
- Нужна in-place сортировка — не подходит, если нельзя выделить дополнительную память
С объяснением логики работы
/**
* Сортировка слиянием (Merge Sort)
* Принцип: рекурсивный подход "разделяй и властвуй" (divide and conquer).
* 1. Делим массив пополам рекурсивно до тех пор, пока не останутся массивы из 1 элемента
* 2. Сливаем (merge) отсортированные подмассивы в один отсортированный массив
* Ключевая идея: легко слить два УЖЕ отсортированных массива в один отсортированный
*/
/**
* Вспомогательная функция для слияния двух отсортированных массивов
* Это "сердце" алгоритма merge sort
*/
function merge(left, right) {
// Результирующий отсортированный массив
const result = [];
// Индексы для прохода по левому и правому массивам
let leftIndex = 0;
let rightIndex = 0;
// Сравниваем элементы из обоих массивов и добавляем меньший в результат
// Продолжаем пока не закончится один из массивов
while (leftIndex < left.length && rightIndex < right.length) {
// Сравниваем текущие элементы из левого и правого массивов
if (left[leftIndex] <= right[rightIndex]) {
// Элемент из левого массива меньше или равен
// Добавляем его в результат и переходим к следующему элементу левого массива
result.push(left[leftIndex]);
leftIndex++;
} else {
// Элемент из правого массива меньше
// Добавляем его в результат и переходим к следующему элементу правого массива
result.push(right[rightIndex]);
rightIndex++;
}
}
// После выхода из цикла один из массивов закончился
// Но во втором могут остаться элементы
// Так как оба массива УЖЕ отсортированы, просто добавляем остатки в конец
// Добавляем оставшиеся элементы из левого массива (если есть)
while (leftIndex < left.length) {
result.push(left[leftIndex]);
leftIndex++;
}
// Добавляем оставшиеся элементы из правого массива (если есть)
while (rightIndex < right.length) {
result.push(right[rightIndex]);
rightIndex++;
}
// Возвращаем объединённый отсортированный массив
return result;
}
/**
* Основная функция сортировки слиянием
* Рекурсивно делит массив и сливает отсортированные части
*/
function mergeSort(arr) {
// БАЗОВЫЙ СЛУЧАЙ: массив из 0 или 1 элемента уже отсортирован
// Это останавливает рекурсию
if (arr.length <= 1) {
return arr;
}
// РЕКУРСИВНЫЙ СЛУЧАЙ: делим массив пополам
// Находим середину массива
const mid = Math.floor(arr.length / 2);
// Делим массив на левую половину (от начала до середины)
const left = arr.slice(0, mid);
// И правую половину (от середины до конца)
const right = arr.slice(mid);
// Рекурсивно сортируем левую половину
// Эта строка будет вызывать mergeSort для всё меньших и меньших массивов
// пока не дойдёт до массивов размером 1
const sortedLeft = mergeSort(left);
// Рекурсивно сортируем правую половину
// То же самое происходит с правой частью
const sortedRight = mergeSort(right);
// Сливаем две отсортированные половины в один отсортированный массив
// К этому моменту и left, и right уже отсортированы
return merge(sortedLeft, sortedRight);
}
// Пример использования
const numbers = [38, 27, 43, 3, 9, 82, 10];
console.log("Исходный массив:", numbers);
const sorted = mergeSort(numbers);
console.log("Отсортированный массив:", sorted);
// Визуализация работы алгоритма:
// [38, 27, 43, 3, 9, 82, 10]
// |
// Делим пополам
// |
// [38, 27, 43] [3, 9, 82, 10]
// | |
// Делим ещё Делим ещё
// | |
// [38] [27, 43] [3, 9] [82, 10]
// | | |
// [27] [43] [3] [9] [82] [10]
// | | |
// Сливаем Сливаем Сливаем
// | | |
// [27, 43] [3, 9] [10, 82]
// | |
// [27, 38, 43] [3, 9, 10, 82]
// | |
// Финальное слияние
// |
// [3, 9, 10, 27, 38, 43, 82]С анализом сложностей
/**
* Сортировка слиянием (Merge Sort) с анализом сложности
*
* ВРЕМЕННАЯ СЛОЖНОСТЬ:
* - Лучший случай: O(n log n) — даже если массив отсортирован, всё равно делит и сливает
* - Средний случай: O(n log n) — стандартный случай
* - Худший случай: O(n log n) — даже обратный порядок не меняет сложность
*
* ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
* - O(n) — требуется дополнительная память для временных массивов при слиянии
* - O(log n) — глубина рекурсивного стека вызовов
* - Итого: O(n) доминирует
*
* ФОРМУЛА СЛОЖНОСТИ (Master Theorem):
* T(n) = 2T(n/2) + O(n)
* где:
* - 2T(n/2) — рекурсивно сортируем две половины
* - O(n) — время на слияние
* Решение: T(n) = O(n log n)
*
* ОСОБЕННОСТИ:
* - Всегда O(n log n) — предсказуемая производительность
* - Стабильный алгоритм
* - НЕ in-place — требует дополнительную память
* - Divide and Conquer подход
*/
/**
* Функция слияния двух отсортированных массивов
*
* ВРЕМЕННАЯ СЛОЖНОСТЬ: O(n + m)
* где n = left.length, m = right.length
* В контексте merge sort: O(n) где n — размер объединяемых массивов
*
* ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ: O(n + m)
* Создаём новый массив размером n + m
*/
function merge(left, right) {
// Создание массива — O(1) операция (выделение памяти)
// Память: O(n + m) для хранения результата
const result = [];
// Инициализация индексов — O(1)
let leftIndex = 0;
let rightIndex = 0;
// Основной цикл слияния
// АНАЛИЗ СЛОЖНОСТИ:
// - Каждая итерация добавляет ровно один элемент в result
// - Всего элементов: left.length + right.length
// - Следовательно, максимум (n + m) итераций
//
// ЛУЧШИЙ СЛУЧАЙ: O(min(n, m))
// Если все элементы одного массива меньше первого элемента другого
// Пример: left=[1,2,3], right=[10,20,30]
//
// ХУДШИЙ СЛУЧАЙ: O(n + m)
// Элементы чередуются: left=[1,3,5], right=[2,4,6]
// Нужно пройти все элементы обоих массивов
while (leftIndex < left.length && rightIndex < right.length) {
// Сравнение — O(1)
// ВАЖНО: используем <=, а не <, для стабильности
// Это гарантирует, что равные элементы из left останутся перед элементами из right
if (left[leftIndex] <= right[rightIndex]) {
result.push(left[leftIndex]); // O(1) амортизированное
leftIndex++;
} else {
result.push(right[rightIndex]); // O(1) амортизированное
rightIndex++;
}
}
// Добавление остатков — O(k) где k — количество оставшихся элементов
// В сумме эти циклы обработают максимум (n + m) элементов
// так как один из массивов уже полностью обработан
while (leftIndex < left.length) {
result.push(left[leftIndex]);
leftIndex++;
}
while (rightIndex < right.length) {
result.push(right[rightIndex]);
rightIndex++;
}
// ИТОГО для merge():
// Время: O(n + m) — каждый элемент обрабатывается ровно один раз
// Память: O(n + m) — создаём новый массив такого же размера
return result;
}
/**
* Основная функция сортировки слиянием
*
* АНАЛИЗ РЕКУРСИИ:
*
* ДЕРЕВО РЕКУРСИИ:
* Уровень 0: [n элементов] — 1 вызов, каждый O(n) работы
* Уровень 1: [n/2] [n/2] — 2 вызова, каждый O(n/2) = O(n) суммарно
* Уровень 2: [n/4] [n/4] [n/4] [n/4] — 4 вызова, каждый O(n/4) = O(n) суммарно
* ...
* Уровень log n: [1][1][1]...[1] — n вызовов, каждый O(1) = O(n) суммарно
*
* Количество уровней: log₂(n)
* Работа на каждом уровне: O(n)
* Общая сложность: O(n) * O(log n) = O(n log n)
*/
function mergeSort(arr) {
// БАЗОВЫЙ СЛУЧАЙ
// Проверка — O(1) операция
// Это "дно" рекурсии, когда массив достаточно мал
if (arr.length <= 1) {
return arr; // O(1) — возвращаем массив как есть
}
// РЕКУРСИВНЫЙ СЛУЧАЙ
// Вычисление середины — O(1)
const mid = Math.floor(arr.length / 2);
// Создание подмассивов — O(n/2) для каждого slice
// slice создаёт новый массив, копируя элементы
// ПАМЯТЬ: создаются новые массивы, но после слияния они больше не нужны
const left = arr.slice(0, mid); // O(n/2) время, O(n/2) память
const right = arr.slice(mid); // O(n/2) время, O(n/2) память
// РЕКУРСИВНЫЕ ВЫЗОВЫ
//
// Каждый вызов обрабатывает половину массива
// T(n) = T(n/2) + T(n/2) + O(n)
// где O(n) — время на slice и merge
//
// ГЛУБИНА РЕКУРСИИ: O(log n)
// Массив делится пополам log₂(n) раз до размера 1
// Примеры:
// - n=8: 8 → 4 → 2 → 1 (3 уровня = log₂8)
// - n=16: 16 → 8 → 4 → 2 → 1 (4 уровня = log₂16)
// - n=1024: 10 уровней
//
// ПАМЯТЬ СТЕКА: O(log n)
// В каждый момент времени активно только log n вызовов
// (путь от корня до листа дерева рекурсии)
const sortedLeft = mergeSort(left); // T(n/2)
const sortedRight = mergeSort(right); // T(n/2)
// СЛИЯНИЕ
// merge() работает за O(n) времени и O(n) памяти
// где n = left.length + right.length
return merge(sortedLeft, sortedRight); // O(n)
// АНАЛИЗ ПАМЯТИ ПО УРОВНЯМ:
//
// На каждом уровне рекурсии создаются временные массивы
// суммарного размера n:
// - Уровень 0: 1 массив размера n
// - Уровень 1: 2 массива размера n/2 (суммарно n)
// - Уровень 2: 4 массива размера n/4 (суммарно n)
//
// Максимальная память используется на самом глубоком уровне:
// - Стек рекурсии: O(log n)
// - Временные массивы: O(n) на каждом активном уровне
// - Итого: O(n)
}
// СРАВНИТЕЛЬНЫЙ АНАЛИЗ С ДРУГИМИ АЛГОРИТМАМИ:
//
// ПО ВРЕМЕНИ:
// Merge Sort: всегда O(n log n) ✓
// Quick Sort: средний O(n log n), худший O(n²)
// Heap Sort: всегда O(n log n)
// Insertion Sort: лучший O(n), худший O(n²)
// Counting Sort: O(n + k) если k=O(n)
//
// ПО ПАМЯТИ:
// Merge Sort: O(n) — много памяти ✗
// Quick Sort: O(log n) — мало памяти ✓
// Heap Sort: O(1) — in-place ✓✓
// Insertion Sort: O(1) — in-place ✓✓
// Counting Sort: O(n + k) — много памяти ✗
//
// СТАБИЛЬНОСТЬ:
// Merge Sort: стабильный ✓
// Quick Sort: нестабильный (можно сделать стабильным)
// Heap Sort: нестабильный
// Insertion Sort: стабильный ✓
// Counting Sort: стабильный ✓
//
// КОГДА ВЫБРАТЬ MERGE SORT:
// ✓ Нужна гарантированная O(n log n) производительность
// ✓ Нужна стабильность
// ✓ Данные на диске (external sorting)
// ✓ Linked lists (последовательный доступ)
// ✗ Ограничения по памяти (используйте Quick Sort или Heap Sort)
// ✗ Малые массивы (используйте Insertion Sort)
// Примеры для демонстрации одинаковой сложности:
// ЛУЧШИЙ СЛУЧАЙ: уже отсортированный массив
// Всё равно O(n log n) — алгоритм не адаптивный
const best = [1, 2, 3, 4, 5, 6, 7, 8];
// n=8, уровней рекурсии=3
// Работа: 8 + 8 + 8 = 24 операций ≈ O(n log n)
// ХУДШИЙ СЛУЧАЙ: обратный порядок
// Та же сложность O(n log n) — merge sort всегда одинаков
const worst = [8, 7, 6, 5, 4, 3, 2, 1];
// n=8, уровней рекурсии=3
// Работа: 8 + 8 + 8 = 24 операций ≈ O(n log n)
// СРЕДНИЙ СЛУЧАЙ: случайный порядок
// Опять O(n log n)
const average = [5, 2, 8, 1, 9, 3, 7, 4];
// n=8, уровней рекурсии=3
// Работа: 8 + 8 + 8 = 24 операций ≈ O(n log n)
// Пример использования
console.log("Best case:", mergeSort(best));
console.log("Worst case:", mergeSort(worst));
console.log("Average case:", mergeSort(average));
// ПРАКТИЧЕСКИЙ ПРИМЕР: сортировка большого массива
const large = Array.from({length: 10000}, () => Math.floor(Math.random() * 10000));
console.time("Merge Sort 10k elements");
mergeSort(large);
console.timeEnd("Merge Sort 10k elements");
// Для n=10000: log₂(10000) ≈ 13.3 уровней
// Операций: 10000 * 13.3 ≈ 133,000