Сортування злиттям (Merge Sort)

Повне пояснення

Коротке пояснення

Merge Sort розбиває масив на дві частини, сортує кожну рекурсивно і потім об’єднує їх у один відсортований масив. Ідея полягає в тому, що об’єднання двох вже відсортованих списків можна виконати за лінійний час.

Аналогія

Уявіть, що ви маєте два купи книг, кожна вже упорядкована за розміром. Щоб отримати одну купу, ви берете найменшу книгу з кожної купи і кладете її в новий список, продовжуючи до тих пір, поки обидві купи не порожні.

Коли застосовувати

• Масив великий, і потрібна гарантована O(n log n) складність.
• Потрібно стабільне сортування (зберігає порядок однакових елементів).
• Пам’ять достатня для додаткового простору O(n).
• Дані не піддаються швидкому вставленню/видаленню, як у бінарному дереві.

Кроки алгоритму

1. Якщо масив має 0 або 1 елемент, повернути його.
2. Знайти середину масиву і розділити на ліву та праву частини.
3. Рекурсивно викликати Merge Sort для кожної половини.
4. Об’єднати дві відсортовані частини у один масив, порівнюючи їх елементи.
5. Повернути об’єднаний масив.

Візуальна інтуїція (текстова)

[4, 1, 3, 2]
├─ розділити → [4, 1] | [3, 2]
│   ├─ розділити → [4] | [1]
│   │   → повернути [1, 4]
│   ├─ розділити → [3] | [2]
│   │   → повернути [2, 3]
│   └─ об’єднати → [1, 4] + [2, 3] = [1, 2, 3, 4]
└─ повернути

Складність

Часова складність: O(n log n) у найгіршому, середньому й кращому випадках. Пам’ятна складність: O(n) через тимчасовий масив під час злиття.

Код (js)

// Merge Sort: рекурсивне розділення і злиття
function mergeSort(array) {
  // Якщо масив має 0 або 1 елемент, він вже відсортований
  if (array.length <= 1) {
    return array;
  }

  // Знаходимо середину масиву для розділення
  const middle = Math.floor(array.length / 2);
  const leftHalf = array.slice(0, middle); // лівий підмасив
  const rightHalf = array.slice(middle);   // правий підмасив

  // Рекурсивно сортуємо обидві половини
  const sortedLeft = mergeSort(leftHalf);
  const sortedRight = mergeSort(rightHalf);

  // Об’єднуємо відсортовані половини
  return merge(sortedLeft, sortedRight);
}

// Функція злиття двох відсортованих масивів
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([4, 1, 3, 2])); // очікуваний результат: [1, 2, 3, 4]

Типові помилки і поради

1. Використання slice без копіювання – slice створює новий масив, тому пам’ять збільшується. Якщо потрібна ін‑плейс оптимізація, використовуйте індекси.
2. Неправильне обчислення середини – Math.floor(array.length / 2) гарантує, що масив розділяється рівномірно.
3. Забуття об’єднання – без функції merge рекурсія не поверне відсортований результат.
4. Перевантаження стеку – для дуже великих масивів можна замінити рекурсію на ітеративний підхід.
5. Нестабільність – Merge Sort стабільний, тому однакові елементи зберігають порядок.

Перевір себе

1. Яка складність Merge Sort у найгіршому випадку?
2. Чому алгоритм стабільний, а Quick Sort ні за замовчуванням?