Що таке 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() зливає два відсортованих масиви в один відсортований масив, порівнюючи елементи з обох масивів.