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

Merge sort — алгоритм сортировки «разделяй и властвуй», который рекурсивно делит массив пополам, сортирует каждую половину и сливает отсортированные части в один массив. Гарантирует O(n log n) во всех случаях.

Зачем нужно

Merge sort — единственная из классических сортировок с гарантированным O(n log n) в худшем случае. Она стабильна (сохраняет порядок равных элементов) и предсказуема по времени. Используется в TimSort (JavaScript, Python, Java).

Где используется

  • Основа TimSort (V8 Array.sort(), Python sorted)
  • Сортировка связных списков (лучше quick sort для них)
  • Внешняя сортировка (файлы, которые не помещаются в RAM)
  • Параллельная сортировка (половины сортируются независимо)

Предпосылки

Алгоритм

1. Если длина массива <= 1 — вернуть (базовый случай)
2. Разделить массив на две половины
3. Рекурсивно отсортировать левую половину
4. Рекурсивно отсортировать правую половину
5. Слить (merge) две отсортированные половины в один массив

Визуализация

Разделение:
        [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]

Слияние (merge):
        [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]

Реализация в JavaScript

Основная версия

function mergeSort(array) {
  // Базовый случай
  if (array.length <= 1) return array;

  // Разделение
  const mid = Math.floor(array.length / 2);
  const left = mergeSort(array.slice(0, mid));
  const right = mergeSort(array.slice(mid));

  // Слияние
  return merge(left, right);
}

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;
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

Краткая версия с concat

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = arr.length >> 1; // побитовый сдвиг = Math.floor(n/2)
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(a, b) {
  const result = ;
  let i = 0, j = 0;

  while (i < a.length && j < b.length) {
    result.push(a[i] <= b[j] ? a[i++] : b[j++]);
  }

  return result.concat(a.slice(i), b.slice(j));
}

Сортировка объектов

function mergeSortBy(array, compareFn) {
  if (array.length <= 1) return array;

  const mid = Math.floor(array.length / 2);
  const left = mergeSortBy(array.slice(0, mid), compareFn);
  const right = mergeSortBy(array.slice(mid), compareFn);

  return mergeBy(left, right, compareFn);
}

function mergeBy(left, right, compareFn) {
  const result = ;
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (compareFn(left[i], right[j]) <= 0) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i), right.slice(j));
}

// Использование
const users = [
  { name: 'Charlie', age: 35 },
  { name: 'Alice', age: 30 },
  { name: 'Bob', age: 30 },
];

const sorted = mergeSortBy(users, (a, b) => a.age - b.age);
// Alice (30) перед Bob (30) — стабильная сортировка!

Пошаговый разбор функции merge

// merge([1, 4, 7], [2, 3, 8])

// i=0, j=0: left[0]=1 <= right[0]=2 → push 1, i=1
// i=1, j=0: left[1]=4 >  right[0]=2 → push 2, j=1
// i=1, j=1: left[1]=4 >  right[1]=3 → push 3, j=2
// i=1, j=2: left[1]=4 <= right[2]=8 → push 4, i=2
// i=2, j=2: left[2]=7 <= right[2]=8 → push 7, i=3
// i=3: left исчерпан, добавляем right[2]=8
// Результат: [1, 2, 3, 4, 7, 8]

Сложность

Случай Время Память Описание
Лучший O(n log n) O(n) Всегда одинаково
Средний O(n log n) O(n) Всегда одинаково
Худший O(n log n) O(n) Всегда одинаково

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

In-place: нет (требует O(n) дополнительной памяти для слияния).

Почему O(n log n)?

Уровень 0: 1 массив × n элементов    = n операций merge
Уровень 1: 2 массива × n/2 элементов = n операций merge
Уровень 2: 4 массива × n/4 элементов = n операций merge
...
Уровень k: 2^k массивов × n/2^k      = n операций merge

Всего уровней: log₂(n)
На каждом уровне: n операций
Итого: n × log₂(n) = O(n log n)

Сравнение с Quick sort

Параметр Merge sort Quick sort
Гарантированная сложность O(n log n) O(n^2) возможно
Средняя сложность O(n log n) O(n log n)
Память O(n) O(log n)
Стабильность Да Нет
Кэш-дружелюбность Хуже Лучше
На практике Предсказуемый Часто быстрее

Частые ошибки

  1. Забывать, что merge sort требует O(n) памяти. Для больших данных это может быть критично
  2. Не использовать <= в merge. left[i] <= right[j] обеспечивает стабильность; < сделает нестабильной
  3. Забывать добавить остаток после основного цикла. Один из массивов закончится раньше — нужно добавить оставшиеся элементы

Практика

  1. Реализуйте merge sort самостоятельно
  2. Реализуйте merge для трёх массивов одновременно (3-way merge)
  3. Подсчитайте количество инверсий в массиве с помощью модифицированного merge sort
  4. Сравните merge sort и quick sort на массиве из 100 000 элементов

Связанные темы

Ресурсы

  • visualgo.net/en/sorting — визуализация
  • Grokking Algorithms, глава 4 (Aditya Bhargava)
  • Introduction to Algorithms (CLRS), глава 2
  • TimSort — гибрид merge sort + insertion sort (Wikipedia)