1 votes 1 votes How many maximum and minimum element comparisons are required to merge 2 sorted arrays of n and m elements into a single sorted array using merge sort procedure? Sambhrant Maurya asked Aug 5, 2018 Sambhrant Maurya 594 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Siddharth Bhardawaj commented Aug 5, 2018 i edited by Siddharth Bhardawaj Aug 12, 2018 reply Follow Share For Maximum comparison => O(m+n-1) = O(m+n). For Minimum comparison => O(min(m,n)). Analyse and study how to find the time complexity of merge sort and merge algorithm. As this are basic concept , you should know these things. 0 votes 0 votes Sambhrant Maurya commented Aug 6, 2018 reply Follow Share I am getting max no of comparisons=m+n. How is it m+n-1? 0 votes 0 votes Siddharth Bhardawaj commented Aug 6, 2018 reply Follow Share Take out the first element of first subarray and first element of second subarray and compare them , if first element of first subarray is lesser than first element of second subarray, then put that element into the one another array ( as mergesort is outplace). same procedure follow again and again until the last element. But see before last element it is already get into their place. So , only one element is left, then no element present that can be compared ( as it is the only element present in the arrray to be compared but unfortunately, one element has been left so for comparison we must require two element to compare). so, total comparison is ,m+n-1 only. Better you should watch video on mergesort on youtube , you will definetely get this. 1 votes 1 votes Prasad babu naik m commented Aug 12, 2018 reply Follow Share Can you provide an example how minimum comparison is max(m,n) 0 votes 0 votes MiNiPanda commented Aug 12, 2018 reply Follow Share It should be min(m,n) not max. Suppose elements in 1st sub array is {1,2} and another subarray is {3,4,5}. Then 1 is compared with 3. Then 1 is inserted into the merged list. 2 is then compared with 3. Then 2 is inserted into the merged list. Then nothing else is left in 1st subarray to be compared. We just copy down the whole 2nd subarray. So 2 comparisons required in this case i.e. min(m,n) =min(2,3) 2 votes 2 votes Siddharth Bhardawaj commented Aug 12, 2018 reply Follow Share Sorry , it was my mistake that I have written max(m,n). I dont know how I made such silly mistake while writing.... Answer is O(min(m,n)).... And thanks for pointing out my mistake...:) 1 votes 1 votes Siddharth Bhardawaj commented Aug 12, 2018 reply Follow Share Check @MiNipanda comments......he has explained briefly with an example.....you will definitely get that.... 0 votes 0 votes Mohamadali commented Oct 14, 2020 reply Follow Share Suppose elements in 1st sub array is {1,2,3} with length m=3 and another sub array is {4,5} with length n=2. Then 1 is compared with 4. Then 1 is inserted into the merged list. 2 is then compared with 4. Then 2 is inserted into the merged list. 3 is then compared with 4. Then 3 is inserted into the merged list. Then nothing else is left in 1st subarray to be compared. We just copy down the whole 2nd subarray. So min(m,n)=min(3,2) is not correct! Generally, minimum element comparisons are required to merge is max(m,n). 0 votes 0 votes Please log in or register to add a comment.