Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що таке сортування злиттям (Merge Sort)?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

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

1. Розділення: рекурсивно ділимо масив на дві половини до підмасивів довжиною 0 або 1.
2. Сортування підмасивів: кожен підмасив сортується тим самим методом.
3. Злиття: два вже відсортовані підмасиви об'єднуються в один відсортований, порівнюючи по одному елементу з кожного боку (два вказівники).
4. База рекурсії: масив довжиною 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);
}

// Приклад
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) без рандомізації/медіани трьох.
- Чи можна паралелити? - так: сортуйте ліву і праву половини в різних потоках/воркерах, а потім виконуйте послідовне злиття.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати899 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.