MERGE SORT
MERGE SORT ALGORITHM
INTRODUCTION
Merge Sort is an sorting algorithm, which is usually utilized in computer engineering. Divide and conquer calculation is also a Merge Sort. It works by recursively separating an issue into at least two sub-issues of something very similar or related type, until these become basic enough to be addressed straightforwardly. The answers for the sub-issues are then joined to give an answer for the first issue. So, Merge Sort divides the array into equal halves and then combines them in a sorted manner.
1.The time complexity of merge sort algorithm is O(nlogn)
2.It is the best for sorting linked lists
3.we can also learn the recursion of analysis and design.
Divide and conquer idea of merge sort
For example we have to sort an array A [m…n] of j integers starting from index m and ending index n.
1.Divide part- sorting problem is divided of size j into two different and equal sub-problems of size j/2. By calculating the mid we can divide problem easily.
Left subproblem-sorting A[] from m to mid
Right subproblem-sorting A[] from mid+1 to n
2.Conquer part-Now we have to solve both sub-problems recursively and sort both the smailer halves
3.Combine part-we must merge both sorted halves to get the final array which is sorted
Merge Sort Implementation
For example there was a function merge sort (int A[],int m,int n) .Now sort the array A[] of input parameters with left and right end.
1.Divide part- Now we have to calculate the mid-value, mid= m+(n-m)/2
2.Conquer part 1-we have to call the same function with mid as the right end and sort the left part recursively of size j/2 i.e, merge sort (A,m,mid).
3.Conquer part 2- we have to call the same function with mid +1 as the left end and sort the right part recursively of size j/2 i.e,merge sort (A,mid+1,n).
4.Combine part- we have to merge both smaller sorted halves into a final sorted array by using function merge(A,m,mid,n).
5.Base case-During recursive cells if we find m==n then the recursion will not go further and back from here and their will be one element left in sub-array ,it is trivially sorted.
Merging algorithm analysis of Time and space complexity
Allocation process of memory = O(1)
Process of data copy = O(n1) + O(n2)
= O(n1+n2)
= O(n)
In the worst case merging loop =O(n1+n2)
= O(n)
In the worst case boundary condition 1= O(n1)
In the worst case boundary condition 2 =O(n2)
Overall time complexity =O(1)+O(n)+O(n)+O(n1)+O(n2)= O(n)
If we observe the merging algorithm time complexity depends on the merging loop of time complexity
Space complexity = O(n1) +O(n2)
= O(n1+n2)
= O(n)
Merge sort visualization example
Merge sort analysis of Time and Space complexity
Let T(j) is the merge sort for j integers of the merge time complexity where j>1 then time complexities are break down as follow
1.Divide part-calculating the middle index takes constant time. Time complexity is O(1).
2.Conquer part- we must solve the two sub-problems by recursively of each size j/2.time complexity of each subproblem is T(j/2). The conquer part of overall time complexity is 2T(j/2).
3.Combine part-merging process of worst-case time complexity is O(n).
For calculating T(j) we need to add all the time complexities
T(j) = O(1) +2T(j/2)+O(j)
= 2T(j/2) + O(j)
= 2T(j/2) + cj
T(j) = c if j =1
T(j) = 2T(j/2) + cj if j>1
Analysis of merge sort using Master Theorem
For the recurrences the direct way to get the solution is Master theorem T(n) = aT(n/b) +O(n^k) where a ≥1 and b>1. There are 3 cases to analysis by master theorem:
(i)f(n) = O(n^k) where k<logb(a) then T(n) = O(n^logb(a))
(ii)f(n) = O(n^k) where k=logb(a) then T(n) = O(n^k*logn)
(iii)f(n) = O(n^k) where k>logb(a) then T(n) = O(n^k)
Now compare the merge sort recurrence
T(n) = 2T(n/2) +cn
T(n) = aT(n/b) + O(n*k)
Here a = 2 and b= 2 (a>1 and b>1)
O(n^k)=cn=O(n)
K=1
Similarly logb(a) =log2(2) =1=k
By this we can say 2nd case of the master theorem satify merge sort recurrence
Time complexity T(n) = O(n^k*logn) = O(n¹*logn)=O(nlogn)
Space complexity =O(n) + O(logn) = O(n)
Applications of a merge sort
1.The main use of merge sort is for sorting linked lists . the case is different mostly because of the distinction in memory portion of clusters and connected records. Not at all like clusters, connected list hubs may not be adjoining in memory. As opposed to a exhibit , in the associated overview, we can install things in the middle in O(1) extra room and O(1) time. Along these lines, the union activity of consolidation sort can be carried out without additional room for connected records.
2.Utilized in External Sorting
Drawbacks of Merge Sort
1.More slow relative to the other sort algorithms for smaller tasks.
2.Merge sort calculation requires an extra memory space of 0(n) for the temporary array.
3.It goes through the entire process even if the array is sorted.
