Merge Sort in Data Structure

Divide and Conquer Sorting:

In terms of Merge Sort, this method has three distinct steps:

Divide: If the input size is too large to deal with in a straightforward manner, divide the data into two or more disjoint subsets.
Recur: Use divide and conquer to solve the subproblems associated with the data subsets.
Conquer: Take the solutions to the sub-problems and “merge” these solutions into a solution for the original problem.

Algorithm for Merge Sort:

Merge Sort consists of two algorithms.
1. This algorithm sorts a set of elements:

Algorithm fnSort(low, high)
{
if(low<high)
{
mid=[(low+high)/2];
fnSort(low, mid);
fnSort(mid+1, high);
fnSort(low, mid, high);
}
} // End of Algorithm

 

2. This algorithm merges two sorted sub-arrays:

Algorithm fnMerge(low, mid, high)
{
h=low;
k=low;
j=mid;
while(h<=mid && j<=high)
{
if(P[h]<=P[j])
{
B[k]=P[h];
h=h+1;
}
else
{
B[k]=P[j];
j=j+1;
}
k=k+1;
}
if(h<mid)
{
for(i=h; i<=mid; i++)
{
B[k]=P[i];
k=k+1;
}
}
else
{
for(i=j; i<=high; i++)
{
B[k]=P[i];
k=k+1;
}
}
for(i=low; i<=high; i++)
P[i]=B[i];
} // End of Algorithm

Time complexity of Merge Sort:

In the merge sort, the call of merge sort and merging does not depend on the order of the elements in the array. So, the best-case, average case and worst-case time complexity are the same in the case of merge sort.

Let total T(n) time be needed to sort the array. That is the function fnMsort(low, high) takes T(n) time where n is the total number of elements in the array. So, the statement fnMsort(low, mid) takes T(n/2) time to finish its execution as here we are dividing the array into two halves each having n/2 elements.

Similarly, fnMsort(mid+1, high) also needs T(n/2) time. Again the statement fnMerge(low, mid, high) for merge operation takes O(n) time. Hence, the recurrence relation to computing the time complexity for the merge sort is:

T(n)=2T(n/2)+c*n
=2[2T(n/2²)+c*n/2]+c*n
=2²T(n/2²)+2c*n
= …………………..
= …………………..
= 2^k(n/2^k)+ kcn
= nT(1)+cnlogn [let 2^k=n, so, k=logn]
= n+cnlogn [for n=1, T(1)=1]
Therefore, T(n)=O(n long)

Space complexity of Merge Sort:

The space complexity of the recursive algorithm for merge sort is O(n logn).

Characteristics of Merge Sort:

1. It is based on a divide and conquer method.
2. Algorithm’s Complexity will return O(n long) in the best, average and worst cases.
3. To execute the algorithm, the extra space required equals the number of elements in the array, space complexity=O(n).
4. The time complexity of algorithm merge is O(n) where n=number of records are merged.