Merge Sort is an example of a divide and conquer algorithm.
A Divide and Conquer algorithm solves a problem using following three steps-
1. Divide: Break the given problem into sub-problems of same type.
2. Conquer: Recursively solve these sub-problems.
3. Combine: Appropriately combine the answers.
In merge sort,the input array is divided in two halves and the function is called again for the two halves.Then,merge() function is used for merging two halves and thus a sorted array is obtained.
Its time complexity is O(N*log(N)) for all cases(worst,best and average).
Algorithm-
Sorting-
1.The middle point of the array is found to divide the array into two halves.
2.MergeSort() is called for the first half.
3.MergeSort() is called for the second half.
4.The two halves sorted in step 2 and step 3 are merged.
Merging-
Let the two arrays to be merged be L[] & R[] and the output is arr[].
[cpp]
k=0;
while( i!=size of L[] && j!=size of R[] )
{
if(L[i]<=R[j]),then arr[k]=L[i] and i and k are incremented by 1.
if(L[i]>R[j]),then arr[k]=R[j] and j and k are incremented by 1.
}
[/cpp]
The remaining elements of L[] are copied, if there are any.
The remaining elements of R[] are copied, if there are any.
Code-
Let arr[] contain all the elements,l denote the starting position of the array,r denote the ending position of the array.m denotes the middle point of the array.
[cpp]
void MergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = (l+r)/2; //middle point of the array is found
MergeSort(arr, l, m); //function called for left sub-array
MergeSort(arr, m+1, r); //function called for right sub-array
merge(arr, l, m, r); //merging of the two sub-arrays
}
}
[/cpp]
[cpp]
void merge(int arr[], int l, int m, int r)
{
int n1,n2,i,j,k;
n1 = m – l + 1; //size of left sub-array
n2 = r – m; //size of right sub-array
//copying contents of left sub-array into a temporary array L[]
for(i = 0; i < n1; i++)
L[i] = arr[l + i];
//copying contents of right sub-array into a temporary array R[]
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++;
}
/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
[/cpp]
Applications-
1.Useful for sorting linked lists.
2.Concept of merge sort can be used in Inversion Count Problem.
