This content has been automatically translated from Ukrainian.
MergeSort is an efficient sorting algorithm that uses the divide-and-conquer principle. It is based on the idea of breaking the input array into smaller parts, sorting each part separately, and then combining them into a sorted array.
The basic idea behind MergeSort is to split the original array in half until the basic case is reached where only one or no element remains in the array. Then the merge process begins with combining two sorted parts to create a new sorted array. This process is repeated by recursively until all parts are completely merged into one sorted array.
One of the main advantages of MergeSort is that it always works with time complexity O(n log n), where n is the number of elements in the original array. This makes it efficient for sorting large data sets.
When and by whom was MergeSort created?
MergeSort was developed by John von Neumann in 1945. However, its publication took place later, in 1948, when his colleague Hermann Goldstine described von Neumann's work during a report at a meeting of the Mathematical Society of America. Thus, the MergeSort algorithm began to gain popularity and became an important part of modern algorithmic knowledge and computer science.
Von Neumann is an outstanding mathematician, physicist, computer scientist and electrical engineer. He made a significant contribution to the development of the theory of calculations, computer architecture and numerical methods. MergeSort is one of the sorting algorithms he developed and has become the basis for numerous variants and optimizations that are still used today.
An example of the MergeSort algorithm (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;
}
//Example use
const arr = [8, 5, 2, 9, 1, 7, 6, 3];
const sortedArr = mergeSort(arr);
console.log(sortedArr);
Result:
[1, 2, 3, 5, 6, 7, 8, 9]
Function mergeSort() recursively bisects the input array, sorts each half with a call mergeSort(), and then combines them using a function merge(). Function merge() merges two sorted arrays into one sorted array, comparing elements from both arrays.
An example of the MergeSort algorithm (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
# Example of use
arr = [8, 5, 2, 9, 1, 7, 6, 3]
sorted_arr = merge_sort(arr)
puts sorted_arr
Result:
[1, 2, 3, 5, 6, 7, 8, 9]
Function merge_sort() recursively bisects the input array, sorts each half with a call merge_sort(), and then combines them using a function merge(). Function merge() merges two sorted arrays into one sorted array, comparing elements from both arrays.
This post doesn't have any additions from the author yet.
