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
p
and store the last index in r
.q
= (p + r)/2
p
to q
and from q + 1
to r
index.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];
}
}
O(nlogn)