Merge Sort is a popular and efficient sorting algorithm that is based on the divide-and-conquer approach. It is a comparison-based sorting algorithm that divides an array into two smaller sub-arrays and then recursively sorts the sub-arrays before merging them back together in a sorted order. The algorithm has a time complexity of O(n log n) and is considered one of the most efficient sorting algorithms available. In this article, we will take a closer look at the Merge Sort algorithm, including its code and explanation in C++.
The Merge Sort algorithm works by dividing an array into two smaller sub-arrays and then recursively sorting each sub-array. Once the sub-arrays are sorted, the algorithm then merges them back together in a sorted order. The process of dividing and merging the array is repeated until the entire array is sorted.
The first step in the Merge Sort algorithm is to divide the array into two smaller sub-arrays. This is done by finding the middle of the array and then dividing it into two smaller sub-arrays. The left sub-array will contain elements from the start of the array to the middle, while the right sub-array will contain elements from the middle to the end of the array.
Once the array is divided into two smaller sub-arrays, the algorithm then recursively sorts each sub-array. This is done by calling the Merge Sort function on each sub-array. This process is repeated until each sub-array contains only one element. At this point, the sub-arrays are considered sorted.
The next step in the Merge Sort algorithm is to merge the two sorted sub-arrays back together. This is done by comparing the first element of each sub-array and then placing the smaller element into a new array. The process is repeated until one of the sub-arrays is empty. At this point, the remaining elements in the other sub-array are placed into the new array.
The process of dividing and merging the array is repeated until the entire array is sorted. The final result is a fully sorted array.
Here is the C++ code for the Merge Sort algorithm:
void mergeSort(int arr[], int left, int right)
{
if (left < right)
{
int middle = (left + right) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
void merge(int arr[], int left, int middle, int right)
{
int i, j, k;
int n1 = middle - left + 1;
int n2 = right - middle;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[middle + 1 + j];
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
