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

MergeSort — элегантный алгоритм с гарантированным O(n log n) в любом случае. Идея: разбить массив пополам до одиночных элементов, затем аккуратно слить части в правильном порядке. Порядок из хаоса через рекурсию.

🔀 Идея: разбить и слить

Сортировка слиянием тоже использует принцип «разделяй и властвуй», но делает это иначе, чем QuickSort. Если QuickSort сначала организует данные (выбирает pivot, делит умно) и потом рекурсирует — то MergeSort сначала слепо делит пополам, а всю умную работу делает при слиянии.

Аналогия: представьте, что вам нужно отсортировать колоду из 8 карт.

1. Разделите колоду на 2 части по 4 карты
2. Каждые 4 разделите на 2 части по 2 карты
3. Каждые 2 разделите на 2 части по 1 карте
4. Теперь у вас 8 отдельных карт — каждая «отсортированная» сама по себе
5. Сливайте пары: берите из двух стопок наименьшую сверху — кладите в результат
6. Сливайте пары побольше: из двух стопок по 2 → стопка из 4
7. Финальное слияние: из двух стопок по 4 → отсортированная колода из 8

📊 Пошаговая визуализация: [5, 3, 8, 1, 4]

Проследим весь процесс для массива [5, 3, 8, 1, 4] шаг за шагом.

💻 Функция merge: слияние двух отсортированных массивов

Вся мощь MergeSort заключена в функции merge. Она принимает два уже отсортированных массива и возвращает один отсортированный. Алгоритм простой: сравниваем первые элементы, берём меньший, двигаем указатель вперёд — повторяем до конца.

function merge(left, right) {
  const result = [];
  let i = 0; // указатель для left
  let j = 0; // указатель для right

  // Пока в обоих массивах ещё есть элементы
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]); // меньший — из левого
      i++;
    } else {
      result.push(right[j]); // меньший — из правого
      j++;
    }
  }

  // Один из массивов закончился — добавляем остаток другого
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result;
}

// Тест:
console.log(merge([3, 5], [1, 4, 8]));
// [1, 3, 4, 5, 8] ✅

Функция merge работает за O(n) — каждый элемент обоих массивов берётся ровно один раз. Это ключ к эффективности всего алгоритма.

💻 Полный алгоритм mergeSort

Теперь добавляем рекурсивную функцию, которая делит массив пополам и вызывает merge:

function merge(left, right) {
  const 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));
}

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);     // правая половина

  // Рекурсивно сортируем каждую половину и сливаем
  return merge(
    mergeSort(left),   // отсортированная левая часть
    mergeSort(right)   // отсортированная правая часть
  );
}

console.log(mergeSort([5, 3, 8, 1, 4]));
// [1, 3, 4, 5, 8]

console.log(mergeSort([10, 2, 7, 5, 1, 9, 3, 6]));
// [1, 2, 3, 5, 6, 7, 9, 10]

🔢 Почему O(n log n) — гарантированно

В отличие от QuickSort, у MergeSort нет «плохого» способа разделить массив. Мы всегда делим строго пополам — это гарантирует log n уровней рекурсии независимо от данных.

Формула: n элементов → log n уровней разбиения → на каждом уровне суммарно n работы при слиянии. Итого: n × log n.

🏛️ Стабильность: важное свойство

Стабильная сортировка сохраняет относительный порядок одинаковых элементов. MergeSort — стабильный: в функции merge при равных элементах мы берём из левого массива (left[i] <= right[j]), что сохраняет исходный порядок равных элементов.

Это важно, когда сортируете объекты по одному полю, сохраняя порядок по другому:

// Ситуация: список задач, отсортированных по приоритету
// Затем сортируем по статусу
const tasks = [
  { id: 1, name: "Задача А", priority: 2, status: "todo" },
  { id: 2, name: "Задача Б", priority: 1, status: "todo" },
  { id: 3, name: "Задача В", priority: 1, status: "done" },
];

// Стабильная сортировка по статусу:
// Задачи с одинаковым статусом сохранят порядок по priority
tasks.sort((a, b) => a.status.localeCompare(b.status));
// Задача Б (priority 1, done) раньше Задачи В (priority 1, done)
// — порядок внутри группы сохранён ✅

🌐 Где MergeSort применяется в реальной жизни

✅ Итоги урока

• MergeSort: фаза разбиения (до одиночных элементов) + фаза слияния (собираем обратно в порядке)
• Функция merge объединяет два отсортированных массива за O(n) — это сердце алгоритма
• Рекурсивная функция mergeSort делит пополам и вызывает merge при подъёме
• Сложность O(n log n) всегда — в лучшем, среднем и худшем случае
• Требует O(n) дополнительной памяти для промежуточных массивов
• Стабильный алгоритм — сохраняет порядок одинаковых элементов
• Используется в БД, внешней сортировке, сортировке связных списков