Алгоритмы с нуля

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

Суть Сортировка слиянием раздели́т массив, рекурсивно сортирует каждую половину, потом объединяет за O(n). Результат: O(n log n) всегда. Стабильна, не на месте, O(n) памяти. Первый вкус divide-and-conquer.

◷ 21 min

Ты видел простые сортировки: выбор, вставка, пузырёк. Все O(n²) и медленные на больших данных. Быстрые алгоритмы (сортировка слиянием, быстрая сортировка) используют трюк: раздели́ массив на куски, реши каждый отдельно, потом объедини решения. Это divide and conquer (раздели и властвуй). Сортировка слиянием — чистейший пример. Раздели́т массив пополам, рекурсивно сортирует каждую половину, потом объединяет обе отсортированные половины за линейное время. Результат O(n log n) — всегда, даже в худшем случае.

Цель

После этого урока ты разбираешься в сортировке слиянием: как объединить две уже отсортированные массивы за O(n) (две указателя), как работает divide-and-conquer, почему слияние всегда O(n log n) (log n уровней раздела, O(n) слияния на каждый уровень), почему оно стабильно (равные элементы остаются в порядке) и не на месте (использует O(n) памяти), и что divide and conquer значит как общий паттерн алгоритма.

Идея

Раздели и властвуй: стратегия

Суть сортировки слиянием: если ты раздели́шь задачу на две независимые подзадачи половинного размера, решишь каждую рекурсивно и объединишь решения, часто получишь намного более быстрый алгоритм.

Сортировка слиянием следует трём шагам:

Раздели (divide): раздели́ массив пополам (или остановись если размер 1).
Властвуй (conquer): рекурсивно вызови сортировку слиянием на каждую половину.
Объедини (combine): объедини две отсортированные половины в один отсортированный массив.

Шаг слияния: объединение двух отсортированных массивов

Сердце сортировки слиянием — функция merge. Даны две уже отсортированные массивы, объедини их в один за O(n) с двумя указателями.

Представь две отсортированные массивы рядом:

Левая: [1, 3, 5]
Правая: [2, 4, 6]

Начни с двух указателей, один в начале каждой. Сравни элементы у обоих. Возьми меньший, сдвинь указатель того массива и повтори:

Левая:   [1, 3, 5]
         ^
Правая:  [2, 4, 6]
         ^
Сравни: 1 < 2. Возьми 1. Указатель левой сдвинется.

Левая:   [1, 3, 5]
            ^
Правая:  [2, 4, 6]
         ^
Сравни: 3 > 2. Возьми 2. Указатель правой сдвинется.

Левая:   [1, 3, 5]
            ^
Правая:  [2, 4, 6]
            ^
Сравни: 3 < 4. Возьми 3. Указатель левой сдвинется.

(продолжаем...)
Результат: [1, 2, 3, 4, 5, 6]

Почему O(n)? Ты проходишь каждый указатель через его массив ровно один раз. Всего шагов = длина левой + длина правой = O(n).

Почему сортировка слиянием O(n log n)

Сложность по времени идёт из двух: сколько уровней раздела и сколько работы на уровень.

Сколько уровней раздела? Массив делится пополам каждый раз: n → n/2 → n/4 → … → 1. Это log n уровней.

Из курса математики Логарифмы

Сколько работы на уровень? На каждом уровне ты объединяешь подмассивы. Общая работа по всем подмассивам на одном уровне O(n) — каждый элемент трогаешь один раз.

Уровень 1 (полный массив): одно объединение, O(n) работы.
Уровень 2 (две половины): два объединения, O(n/2) + O(n/2) = O(n) работы.
Уровень 3 (четыре четвёрки): четыре объединения, O(n/4) × 4 = O(n) работы.
…
Уровень log n: много маленьких объединений, всё ещё O(n) работы в целом.

Всего: log n уровней × O(n) работы за уровень = O(n log n).

Стабильность и память

Сортировка слиянием стабильна: при объединении если оба указателя показывают на равные элементы, берёшь из левого массива первым. Это сохраняет порядок равных элементов.

Сортировка слиянием не на месте: ты создаёшь новый массив при слиянии чтобы удерживать результат. Это стоит O(n) памяти. Рекурсивная сортировка слиянием тоже использует O(log n) памяти для стека вызовов. Всего: O(n).

Код

Давайте напишем сортировку слиянием с нуля.

Шаг 1: Объедини две отсортированные массивы

function merge(left, right) {
  const result = [];
  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++;
    }
  }

  // Если в левом ещё есть, добавь
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }

  // Если в правом ещё есть, добавь
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result;
}

Обрати внимание: left[i] <= right[j] (не <) сохраняет стабильность. Если элементы равны, возьми из левого первым.

Шаг 2: Сортировка слиянием рекурсивно

function mergeSort(arr) {
  // Базовый случай: массив размера 0 или 1 уже отсортирован
  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);
}

Это полный алгоритм. Рекурсия заканчивается когда массив размера 0 или 1 (уже отсортирован).

Давайте запустим:

function mergeSort(arr) {
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);
}

const unsorted = [38, 27, 43, 3, 9, 82, 10];
const sorted = mergeSort(unsorted);
console.log("Исходный:", unsorted);
console.log("Отсорт: ", sorted);

// Проверь стабильность
const items = [
{ val: 3, id: 'a' },
{ val: 1, id: 'b' },
{ val: 3, id: 'c' },
{ val: 2, id: 'd' }
];

function mergeSortStable(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSortStable(arr.slice(0, mid));
const right = mergeSortStable(arr.slice(mid));
return mergeStable(left, right);
}

const sorted2 = mergeSortStable(items);
console.log("Стабильная сортировка (две 3 остаются в порядке a, потом c):");
sorted2.forEach(x => console.log(`  val=${x.val}, id=${x.id}`));

Вывод

Пошаговый разбор

Давайте трассируем сортировку слиянием на маленьком массиве: [38, 27, 43, 3].


      1
      function mergeSort(arr) {
    

      2
        if (arr.length <= 1) return arr;
    

      3
        const mid = Math.floor(arr.length / 2);
    

      4
        const left = mergeSort(arr.slice(0, mid));
    

      5
        const right = mergeSort(arr.slice(mid));
    

      6
        return merge(left, right);
    

      7
      }

Сложность

Аспект	Значение
Время (лучший)	O(n log n)
Время (средний)	O(n log n)
Время (худший)	O(n log n)
Память	O(n)
Стабильна?	Да
На месте?	Нет

Почему всегда O(n log n)?

В отличие от сортировки выбором (всегда O(n²)) или вставкой (O(n) лучше, O(n²) худше), сортировка слиянием не меняется от порядка входа. Она всегда делит массив пополам log n раз, и каждый уровень слияния стоит O(n). Результат всегда O(n log n) — нет лучшего случая, нет худшего, просто O(n log n).

Стабильность:

Сортировка слиянием сохраняет порядок равных элементов. При слиянии и оба указателя на равные значения, берёшь из левого массива первым. Это гарантирует стабильность.

Память:

Сортировка слиянием использует O(n) доп. памяти чтобы создать временные массивы при слиянии. Если входной массив размером n, ты выделяешь примерно n элементов памяти. Рекурсия добавляет O(log n) на стеке (глубина рекурсии = log n). Всего: O(n).

Это компромисс: сортировка слиянием быстра и предсказуема, но использует доп. память.

Практика 0 / 5

Почему сортировка слиянием O(n log n) даже когда вход уже отсортирован?

При слиянии двух отсортированных массивов, почему две указатели вместо поиска каждого элемента?

Сортировка слиянием использует O(n) доп. памяти. Почему это хуже чем выбор (O(1))?

Является ли сортировка слиянием стабильной? То есть равные элементы сохраняют порядок?

Сколько уровней раздела случается при сортировке слиянием массива из 16 элементов?

lesson.inset.advantage

Когда использовать сортировку слиянием. Сортировка слиянием O(n log n) всегда, делая её предсказуемой и быстрой на больших данных. Она стабильна, так что сохраняет порядок (полезно при сортировке по нескольким ключам). Настоящие базы и системы часто используют сортировку слиянием или варианты. Минус: O(n) доп. памяти. Используй когда скорость критична и память есть. Для огромных данных лучше in-place алгоритмы как quicksort (хотя он не стабильный).

lesson.inset.pattern

Divide and conquer как стратегия. Сортировка слиянием — первый divide-and-conquer алгоритм что ты видишь. Паттерн: раздели задачу на независимые подзадачи, решай каждую рекурсивно, объедини решения. Это работает для многих задач: поиск в сбалансированном дереве, умножение больших чисел, поиск ближайшей пары точек. Ключ: подзадачи должны быть независимы (решение одной не влияет другую), и объединение должно быть эффективно.

Проверь себя

Викторина

Нужно отсортировать массив в миллион элементов и у тебя 2 GB RAM. Массив 800 MB. Что лучше: сортировка слиянием (нужно 800 MB доп) или выбор (O(1) доп)?

Итог

Сортировка слиянием раздели́т массив пополам, рекурсивно сортирует каждую половину, потом объединяет вместе.

Шаг слияния берёт два отсортированных массива и объединяет их за O(n) с двумя указателями: ходишь оба, сравниваешь, берёшь меньший.

Сложность по времени: O(n log n) всегда (log n уровней раздела, O(n) работа за уровень). Никогда O(n²), даже на плохом входе.

Память: O(n) для временных массивов при слиянии.

Стабильная: Да. Равные элементы сохраняют порядок.

На месте: Нет. Нужна O(n) доп. памяти.

Раздели и властвуй: Ключевое озарение — раздели пополам, реши каждую половину независимо, объедини. Быстро и мощно. Этот паттерн работает для многих алгоритмов за пределами сортировки.

Почему выучить? Сортировка слиянием учит divide and conquer, один из самых важных дизайна алгоритмов стратегий. Она ещё показывает O(n log n), класс сложности что видишь в многих настоящих системах.

Продолжить восхождение ↑Быстрая сортировка