Introduction:
Sorting is a fundamental operation in computer science that is used to arrange elements in a particular order.
Merge sort is one of the most popular sorting algorithms that uses a divide-and-conquer approach to sort an array.
In this blog, we will discuss the definition of the merge sort algorithm, the problem statement it solves, and its pros and cons. We will also provide an implementation of the merge sort algorithm in C++.
Definition:
Merge sort is a divide-and-conquer algorithm that works by repeatedly dividing the input array into smaller subarrays until each subarray contains just one element.
It then merges the subarrays back together in a sorted order. The merge sort algorithm is called a stable sort, which means that it maintains the relative order of equal elements in the sorted array.
Problem Statement:
The problem that merge sort solves is how to efficiently sort an unsorted array. We can use a brute-force approach to sort an array by repeatedly comparing adjacent elements and swapping them if they are in the wrong order.
However, this approach has a time complexity of O(n^2), which can be slow for large arrays. Merge sort provides a more efficient algorithm to sort an array.
Brute Force:
The brute-force approach to sorting an array involves iterating through each pair of elements and swapping them if they are in the wrong order.
The time complexity of this approach is O(n^2), which means that the time required to sort the array grows quadratically with the size of the array.
When and why to use Merge Sort:
We should use merge sort when we have an unsorted array and need to sort it efficiently.
Merge sort is an efficient algorithm for sorting large arrays, and it has a time complexity of O(n log n), which is much faster than the O(n^2) time complexity of the brute-force approach.
Algorithm:
The merge sort algorithm works by dividing the input array in half, sorting each half recursively, and then merging the sorted halves back together to create a fully sorted array.
The algorithm works by repeatedly dividing the input array in half until each subarray contains only one element.
It then merges adjacent subarrays, sorting them in the process, until the entire array has been sorted.
Here is the implementation of the merge sort algorithm in C++:
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
Pros and Cons:
Pros of merge sort:
The merge sort algorithm has several advantages over the brute-force approach.
It has a time complexity of O(n log n), which is much faster than the O(n^2) time complexity of the brute-force approach.
It is also more efficient in terms of space complexity since it does not require any additional memory beyond the input array.
Cons of merge sort:
However, merge sort has a few disadvantages as well.
It requires additional memory to store the subarrays during the merge operation, which can be a problem for large arrays.
It also has a higher overhead due to the recursive calls, which can impact its performance for small arrays.
Finally:
In conclusion, merge sort is a powerful algorithm for sorting an unsorted array. It provides a more efficient alternative to the brute-force approach by using a divide-and-conquer strategy. Merge sort has a time complexity of O(n log n), which makes it an efficient sorting algorithm for large arrays. However, it requires additional memory and has a higher overhead due to the recursive calls.