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 splitting the input array into smaller parts, sorting each part separately, and then merging them into a sorted array.
The main idea of MergeSort is to split the original array in half until the base case is reached, where there is only one or no element left in the array. Then the merging process begins by combining two sorted parts to create a new sorted array. This process is repeated recursively until all parts are fully merged into one sorted array.
One of the main advantages of MergeSort is that it always operates with a time complexity of O(n log n), where n is the number of elements in the input array. This makes it efficient for sorting large arrays of data.
When and by whom was MergeSort created?
MergeSort was developed by John von Neumann in 1945. However, its publication occurred later, in 1948, when his colleague Hermann Goldstine described von Neumann's work during a presentation at a meeting of the American Mathematical Society. Thus, the MergeSort algorithm began to gain popularity and became an important part of modern algorithmic knowledge and computer science.
Von Neumann was a prominent mathematician, physicist, computer scientist, and electrical engineer. He made significant contributions to the development of computation theory, 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.
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 usage
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]
The mergeSort() function recursively splits the input array in half, sorts each half by calling mergeSort(), and then merges them using the merge() function. The merge() function merges two sorted arrays into one sorted array by comparing elements from both arrays.
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 usage
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]
The merge_sort() function recursively splits the input array in half, sorts each half by calling merge_sort(), and then merges them using the merge() function. The merge() function merges two sorted arrays into one sorted array by comparing elements from both arrays.
This post doesn't have any additions from the author yet.
