Що таке сортування злиттям (Merge Sort)?

АлгоритмиJunior~3 хв читання

Що таке сортування злиттям (Merge Sort)?

Коротка відповідь

Сортування злиттям - це стабільний алгоритм «розділяй і володарюй»: він рекурсивно ділить масив навпіл, сортує частини і зливає їх в один відсортований. Забезпечує O(n log n) за часом у всіх випадках, вимагає O(n) додаткової пам'яті і дає передбачувану, рівномірну продуктивність.

Детальний розбір

Ідея алгоритму (divide and conquer)

Розділення: рекурсивно ділимо масив на дві половини до підмасивів довжиною 0 або 1.
Сортування підмасивів: кожен підмасив сортується тим самим методом.
Злиття: два вже відсортовані підмасиви об'єднуються в один відсортований, порівнюючи по одному елементу з кожного боку (два вказівники).
База рекурсії: масив довжиною 0 або 1 уже відсортований.

Складність і ключові властивості

Час: O(n log n) у найкращому, середньому і найгіршому випадках.
Пам'ять: O(n) додаткової пам'яті для масивів (класична реалізація).
Стабільність: так (зберігає відносний порядок рівних елементів за коректної операції злиття).
Детермінованість: однакова асимптотика для будь-яких вхідних даних, без деградації, як у QuickSort.
Гарна для зв'язних списків: може працювати з O(1) дод. пам'яті, оскільки потрібна лише перестановка посилань.
Підходить для зовнішнього сортування: ефективно працює з файлами/потоками (обмежена RAM).
Паралелізація: легко паралелиться на етапі рекурсивного сортування половин.

Властивість	Значення
Найкращий/середній/найгірший випадки за часом	O(n log n)
Дод. пам'ять (масив)	O(n)
Стабільність	Так (за умови порівняння <= у злитті)
Адаптивність до майже відсортованих даних	Ні (класична версія)

Коли використовувати, а коли ні

Використовувати: коли важлива стабільність і передбачуване O(n log n) у найгіршому випадку (наприклад, сортування за кількома ключами).
Використовувати: під час роботи зі списками і зовнішнього сортування великих даних, що не вміщуються в пам'ять.
Обережно: на масивах вимагає O(n) пам'яті; якщо пам'ять обмежена, розгляньте HeapSort (in-place, але нестабільний) або QuickSort (середній випадок швидший, але найгірший - O(n^2)).

Рекурсивна реалізація (top-down, JS)

javascript

// Стабільне сортування злиттям (top-down)
function mergeSort(arr) {
  if (arr.length <= 1) return arr.slice(); // копія, щоб не мутувати вихідний масив
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    // '<=' забезпечує стабільність: елементи з left йдуть першими за рівності
    if (left[i] <= right[j]) {
      res.push(left[i++]);
    } else {
      res.push(right[j++]);
    }
  }
  while (i < left.length) res.push(left[i++]);
  while (j < right.length) res.push(right[j++]);
  return res;
}

// Приклад
const arr = [5, 2, 4, 6, 1, 3, 2];
console.log(mergeSort(arr)); // [1, 2, 2, 3, 4, 5, 6]

Ітеративна (bottom-up) реалізація (JS)

Bottom-up версія уникає рекурсії: спочатку зливаємо блоки розміру 1, потім 2, 4, 8 і так далі.

javascript

function mergeSortBottomUp(a) {
  const n = a.length;
  const aux = new Array(n);
  for (let sz = 1; sz < n; sz <<= 1) {
    for (let lo = 0; lo < n - sz; lo += sz << 1) {
      const mid = lo + sz;
      const hi = Math.min(lo + (sz << 1), n);
      mergeRange(a, aux, lo, mid, hi);
    }
  }
  return a;
}

function mergeRange(a, aux, lo, mid, hi) {
  // Копіюємо в буфер
  for (let t = lo; t < hi; t++) aux[t] = a[t];
  let i = lo, j = mid, k = lo;
  while (i < mid && j < hi) {
    if (aux[i] <= aux[j]) a[k++] = aux[i++];
    else a[k++] = aux[j++];
  }
  while (i < mid) a[k++] = aux[i++];
  while (j < hi) a[k++] = aux[j++];
}

// Приклад
const arr2 = [7, 1, 4, 9, 0, 3, 8, 2, 6, 5];
console.log(mergeSortBottomUp(arr2));

Оптимізація виділень пам'яті: єдиний буфер

Щоб не створювати тимчасові масиви на кожному кроці рекурсії, передавайте єдиний допоміжний буфер.

javascript

function mergeSortWithBuffer(a) {
  const aux = new Array(a.length);
  sort(a, aux, 0, a.length);
  return a;
}

function sort(a, aux, lo, hi) {
  if (hi - lo <= 1) return;
  const mid = lo + ((hi - lo) >> 1);
  sort(a, aux, lo, mid);
  sort(a, aux, mid, hi);
  mergeRanges(a, aux, lo, mid, hi);
}

function mergeRanges(a, aux, lo, mid, hi) {
  for (let t = lo; t < hi; t++) aux[t] = a[t];
  let i = lo, j = mid, k = lo;
  while (i < mid && j < hi) {
    if (aux[i] <= aux[j]) a[k++] = aux[i++];
    else a[k++] = aux[j++];
  }
  while (i < mid) a[k++] = aux[i++];
  while (j < hi) a[k++] = aux[j++];
}

Сортування зв'язаного списку злиттям (коротко)

Розбиття списку на дві половини робиться через повільний/швидкий вказівники (slow/fast).
Злиття - це переналаштування посилань next; дод. пам'ять - O(1), алгоритм залишається стабільним.

Типові питання на співбесіді та ключові відповіді

Чому O(n log n)? - log n рівнів поділу, на кожному рівні сумарно обробляємо n елементів під час злиття: n × log n.
Що таке стабільність? - рівні елементи зберігають вихідний порядок. У merge перевіряйте умову через '<='.
Чому не in-place? - класичне злиття вимагає тимчасового буфера; існують складні in-place варіанти, але вони рідко використовуються через складність і константи.
Порівняння з QuickSort: MergeSort стабільний і гарантує O(n log n) у найгіршому випадку, але вимагає O(n) пам'яті; QuickSort зазвичай швидший на практиці і in-place, але найгірший випадок - O(n^2) без рандомізації/медіани трьох.
Чи можна паралелити? - так: сортуйте ліву і праву половини в різних потоках/воркерах, а потім виконуйте послідовне злиття.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.