## Merge Sort

Merge sort is a sorting algorithm that works on the principle of Divide and Conquer. The array or list of elements is repeatedly broken down into several subarrays until each subarray consists of a single element. Then these subarrays are merged in a way such that the result is a sorted list.

Since the merge sort algorithm uses recursion to sort a given set of elements, it consumes less time.

*Steps*

- Store the starting index of thearray in
`p`

and store the last index in`r`

. - Store the middle index of array in
`q`

=`(p + r)/2`

- Break the array into two subarrays, from
`p`

to`q`

and from`q + 1`

to`r`

index. - Divide these 2 subarrays again, just like the main array was divided.
- Continue dividing into subarrays until subarrays of single elements get created.
- Now start merging the arrays.

*Code*

```
void MergeSort(int A[], int p, int r)
{
int q;
if(p < r)
{
q = (p + r) / 2;
MergeSort(A, p, q);
MergeSort(A, q+1, r);
merge(A, p, q, r);
}
}
// function to merge the subarrays
void merge(int A[], int p, int q, int r)
{
int B[5]; //sAme size of A[]
int i, j, k;
k = 0;
i = p;
j = q + 1;
while(i <= q && j <= r)
{
if(A[i] < A[j])
{
B[k] = A[i];
k++;
i++;
}
else
{
B[k++] = A[j++];
}
}
while(i <= q)
{
B[k++] = A[i++];
}
while(j <= r)
{
B[k++] = A[j++];
}
for(i=r; i >= p; i--)
{
A[i] = B[--k];
}
}
```