Дисклеймер

Інформація на сайті tseivo.com є суб'єктивною та відображає особисті погляди та досвід авторів та авторок блогів.

Використовуйте цей ресурс як одне з декількох джерел інформації під час своїх досліджень та прийняття рішень. Завжди застосовуйте критичне мислення. Людина сама несе відповідальність за свої рішення та дії.

Що таке MergeSort? Коли та ким створений? Як саме працює MergeSort?

MergeSort - це ефективний алгоритм сортування, який використовує принцип "розділяй та володарюй". Він базується на ідеї розбиття вхідного масиву на менші частини, сортуванні кожної частини окремо, а потім об'єднанні їх у відсортований масив.
Основна ідея MergeSort полягає у розбитті вихідного масиву навпіл, поки не буде досягнуто базового випадку, коли в масиві залишився лише один або жодного елементу. Потім процес злиття (merge) починається з об'єднання двох відсортованих частин із створенням нового відсортованого масиву. Цей процес повторюється рекурсивно до повного злиття всіх частин в один відсортований масив.
Один з основних переваг MergeSort полягає у тому, що він завжди працює з часовою складністю O(n log n), де n - кількість елементів у вихідному масиві. Це робить його ефективним для сортування великих масивів даних.

Коли та ким створений MergeSort?

MergeSort був розроблений Джоном фон Нейманом (John von Neumann) у 1945 році. Однак його публікація відбулася пізніше, в 1948 році, коли його колега Герман Голдштайн (Hermann Goldstine) описав роботу фон Неймана під час доповіді на засіданні Математичного товариства Америки. Таким чином, алгоритм MergeSort почав набувати популярності і став важливою частиною сучасних алгоритмічних знань і комп'ютерної науки.
Фон Нейман - видатний математик, фізик, комп'ютерний вчений та електротехнік. Він зробив значний внесок в розвиток теорії обчислень, архітектури комп'ютерів та чисельних методів. MergeSort є одним з алгоритмів сортування, який він розробив, і став основою для численних варіантів та оптимізацій, які використовуються і досі.

Приклад MergeSort алгоритму (JavaScript).

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const mergedArr = [];
  let i = 0;
  let j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      mergedArr.push(left[i]);
      i++;
    } else {
      mergedArr.push(right[j]);
      j++;
    }
  }
  
  while (i < left.length) {
    mergedArr.push(left[i]);
    i++;
  }
  
  while (j < right.length) {
    mergedArr.push(right[j]);
    j++;
  }
  
  return mergedArr;
}

// Приклад використання
const arr = [8, 5, 2, 9, 1, 7, 6, 3];
const sortedArr = mergeSort(arr);
console.log(sortedArr);
Результат:
[1, 2, 3, 5, 6, 7, 8, 9]
Функція mergeSort() рекурсивно розбиває вхідний масив навпіл, сортує кожну половину викликом mergeSort(), а потім об'єднує їх за допомогою функції merge(). Функція merge() зливає два відсортованих масиви в один відсортований масив, порівнюючи елементи з обох масивів.

Приклад MergeSort алгоритму (Ruby).

def merge_sort(arr)
  return arr if arr.length <= 1

  mid = arr.length / 2
  left = arr[0...mid]
  right = arr[mid..-1]

  merge(merge_sort(left), merge_sort(right))
end

def merge(left, right)
  merged_arr = []
  i = 0
  j = 0

  while i < left.length && j < right.length
    if left[i] <= right[j]
      merged_arr << left[i]
      i += 1
    else
      merged_arr << right[j]
      j += 1
    end
  end

  while i < left.length
    merged_arr << left[i]
    i += 1
  end

  while j < right.length
    merged_arr << right[j]
    j += 1
  end

  merged_arr
end

# Приклад використання
arr = [8, 5, 2, 9, 1, 7, 6, 3]
sorted_arr = merge_sort(arr)
puts sorted_arr
Результат:
[1, 2, 3, 5, 6, 7, 8, 9]
Функція merge_sort() рекурсивно розбиває вхідний масив навпіл, сортує кожну половину викликом merge_sort(), а потім об'єднує їх за допомогою функції merge(). Функція merge() зливає два відсортованих масиви в один відсортований масив, порівнюючи елементи з обох масивів.
📝 Більше публікацій: