What is Merge Sort in DAA |Algorithm |Complexity
What is Merge Sort in DAA.
Merge sort is referred as sorting algorithm that works by dividing an array into smaller sub-arrays / sub-lists , sorting each sub-arrays or sub-lists. And then merging the sorted sub-arrays / sub-lists into one final array or list.
It is comparison based sorting technique.It is following “Divide and Conquer” stratergy.
If we want to sort a single array or list by using Merge Sort, Firstly, divide the array or list into two parts by using tree like Data-Structure. After dividing we combine single array/list into the resultant sorted array/list.
Note:- Merge Sort is not use usually due to increase in complexity |
Algorithm:
-----> Merge_Sort(A, beg,end)
{
If (beg <end)
{
mid = (big+end)/2
Merge_Sort(A,beg,mid)
Merge_Sort(A,mid+1,end)
}
Merge_Sort(A,beg,mid,end)
end if
{
return
}
}
Merge_Sort(A,beg,mid,end)
PA = beg
PB = mid + 1
PC = beg
Repeat while(PA <= mid & PB <= end)
{
If (A[PA] <= B[PB])
{
C[PC] = A[PA]
PA = PA + 1
}
else
C[PC] = B[PB]
PB = PB + 1
end if
PC = PC + 1
}
If P[A] > mid
{
Repeat for I = PA to mid
C[PC] = A[I]
PC = PC + 1
end for
Repeat for J = PB to end
C[PC] = B[J]
PC = PC + 1
end for
end if
return
}
Complexity:
n(log n ) or O(n log n)
Steps of Merge Sort
Example 1:
32 | 42 | 68 | 48 | 69 | 90 | 80 |
Solution:-
Step 1: Rename the 0th index as the beg and the nth (last element) as end.
32 | 42 | 68 | 48 | 69 | 90 | 80 |
↓ ↓
beg end
Step 2: Use the formula (Beg+end)/2 . And Separate them in two parts as show in this steps
Step 3: At last the Array / list is be in series.
32 | 42 | 48 | 68 | 69 | 80 | 90 |
Question 1:
38 | 27 | 43 | 10 |
Question 2:
5 | 4 | 1 | 6 | 3 | 2 | 9 | 8 |