The Merge Sort algorithm is one of the most popular algorithms for sorting an array. Merge Sort algorithm is based on the principle of divide and conquer.
This algorithm is a bit complex. Here, we divide the unsorted array into two halves. Again, the two halves are divided into two halves. This process continues till the smallest blocks are received and no further division is possible.
Then, we merge these blocks in such a way that the resulting blocks are sorted among themselves. This is done till the array of the initial size is received. On completion of this, we will see that the array is sorted.
We will now understand the codes for this algorithm –
#include <iostream>
using namespace std;
void merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
int i, j, k;
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[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);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {5,18,3,23,2,6};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
cout << "Sorted array: \n";
printArray(arr, size);
return 0;
}
Output –
2,3,5,6,18,23
Time Complexity of the Merge sort algorithm –
For this algorithm, the time complexity for all three cases is the same.
Best Time Complexity – O(n*log n)
Average Time Complexity – O(n*log n)
Worst Time Complexity – O(n*log n)
Space Complexity of the Merge sort algorithm–
The space complexity for this algorithm is O(n). This means that this algorithm takes up a lot of space and may slow down operations for the last data sets.
So, in this article, we learned about the Merge Sort Algorithm. This algorithm is also used at –
- Inversion count problem
- External sorting
- E-commerce applications.
