What is Merge Sort?

[aastha]

What is Merge Sort?

[aastha]

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

[Author]

Posts