Сортировка слиянием

Классический алгоритм «разделяй и властвуй»: делит массив пополам, рекурсивно сортирует части и сливает их.

Идея алгоритма

Алгоритм рекурсивно делит массив на две части, пока не останутся массивы длины 1 (они уже отсортированы). Затем пары отсортированных массивов последовательно сливаются в один, сохраняя порядок элементов.

Асимптотика:

Время (любой случай): O(n log n)
Память: O(n) — требуется дополнительный массив для слияния
Стабильная сортировка

Когда использовать

Для больших массивов, когда важна стабильность;
Когда доступ к памяти более-менее равномерный (не in-place);
В качестве базового алгоритма в стандартных библиотеках.

Плюсы

Гарантированная сложность O(n log n) в любом случае;
Стабильная сортировка — порядок равных элементов сохраняется;
Хорошо параллелится и предсказуемо работает на любых данных.

Минусы

Требуется дополнительная память O(n);
Реализация сложнее, чем у простых сортировок;
Не является in-place (обычно создаёт новые массивы).

Пример кода

function merge(left, right) {
  const result = [];
  let i = 0, 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++;
    }
  }

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

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

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

  return merge(left, right);
}

Попробуй самостоятельно написать алгоритм, а затем сравнить

НазадСортировка вставками ВпередБыстрая сортировка

Полезные темы

Рекомендуем изучить эти темы для лучшего понимания