Как работает MergeSort

Когда вы начинаете разбираться в алгоритмах, рано или поздно сталкиваетесь с задачей сортировки. И тут появляется MergeSort — одна из самых стабильных и предсказуемых стратегий. Вместо того чтобы искать самый маленький элемент и перемещать его в начало (как делают другие алгоритмы), MergeSort идёт другим путём:

🔘 Сначала делим массив пополам.
🔘 Потом каждую половину — ещё раз пополам.
🔘 Повторяем, пока не получим массивы длиной по одному элементу.
🔘 После этого начинаем собирать обратно — берём по два массива и сливаем их в один отсортированный.

Каждый этап сборки — это аккуратное сравнение элементов. И на выходе получается отсортированный массив. Алгоритм работает быстро и одинаково стабильно — как с упорядоченными, так и с хаотичными данными. Его скорость:

O(n log n) — и в среднем, и в худшем случае.

Это делает его хорошим выбором, когда вам нужно надёжно отсортировать большой объём данных.

Вот код на чистом JavaScript, в котором MergeSort реализован в виде двух функций: mergeSort и merge.

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

  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];

  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  return result.concat(left, right);
}

// Пример использования:
const unsorted = [7, 3, 9, 1, 4];
const sorted = mergeSort(unsorted);
console.log(sorted); // [1, 3, 4, 7, 9]

Что здесь важно понять:

0️⃣ mergeSort рекурсивно делит массив до тех пор, пока не останется по одному элементу.
1️⃣ merge берёт два отсортированных массива и объединяет их в новый, тоже отсортированный.
3️⃣ Всё это повторяется до тех пор, пока не получится один отсортированный массив.

MergeSort — отличный пример того, как можно эффективно решать сложные задачи, используя простую логику: «разделяй и властвуй». Даже если вы только начинаете знакомство с алгоритмами, вы с лёгкостью разберётесь в этом подходе. Он стабилен, понятен, и легко реализуется на любом языке — например, как вы только что увидели, на JavaScript.

#простымисловами #алгоритмы