Merge sort is used to sort element of an array. In merge sort the existing array is divided into two equal halves which are sorted (result of sub-problem) separately and merged again to give the array in sorted form.
Merge sort uses divide and conquer approach.
Steps Involved: –
Array- A, Size- n,
1. Divide the A in two halves A1, A2 containing
• n/2 elements each if n is even.
• First (n-1)/2 and last (n+1)/2 elements respectively.
2. Repeat Step 1 on A1 and A2 separately in Step 1 until size of A1=1 and size of A2= 1.
3. Merging A1 and A2 into A.
initialize i,j,k= 0.
while(i< sizeof(A1) && j<sizeof(A2))
while(i< sizeof(A1)) //if(sizeof(A1)> sizeof(A2)
while(j<sizeof(A2)) //if(sizeof(A2)> sizeof(A1)
Size decreases by a factor of 2 for each sub problem and there are two recursive calls made at each step therefore,
T(n)= 2T(n/2) + cn
Therefore time complexity of merge sort is of the order O(n log(n)).