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))

If(A1[i]<= A2[j])

A[k]= A1[i]

i++, k++

else

A[k]= A2[j]

j++, k++

while(i< sizeof(A1)) //if(sizeof(A1)> sizeof(A2)

A[k]= A1[i]

k++, i++

while(j<sizeof(A2)) //if(sizeof(A2)> sizeof(A1)

A[k]= A1[j]

k++, j++

**Time Complexity**

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)).