Base/Knowledges/IT/Алгоритмы/Сортировки/Сортировка слиянием (Merge Sort).md

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

! Эффективность O(n) = O(n*log(n))

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

function mergeSort(arr) {
  // Базовый случай: массив из 0 или 1 элемента уже отсортирован
  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 = [];
  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++;
    }
  }

  // Добавляем оставшиеся элементы (если есть)
  return result
    .concat(left.slice(i))
    .concat(right.slice(j));
}

Источники

• Стивен Скиена - Алгоритмы. Руководство по разработке