0 votes 0 votes What is the minimum and maximum number of comparisons required to merge two lists of size m and n ? Algorithms merging + – Vipin Rai asked Nov 11, 2018 retagged Jun 24, 2022 by Lakshman Bhaiya Vipin Rai 473 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Hemanth_13 commented Nov 11, 2018 reply Follow Share In Best case example: List1 12 List2 345678 it needs 2 comparisons==> min(m,n) example: list1 123456 list2 78 this needs 6 comparisons but this not the best case In worst case List1 1357 List2 2468 it needs 7 comparisons==> m+n-1 3 votes 3 votes aambazinga commented Nov 11, 2018 reply Follow Share bro, they have not given anything about whether the list is sorted or unsorted... hence taking the worst case that the link is unsorted, #comparisons would be O(mlogm+nogn). 0 votes 0 votes Hemanth_13 commented Nov 11, 2018 reply Follow Share Yes all the explanation was given for merge routine of merge sort(i.e. for sorted lists) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Minimum = min(m,n) Mximum= m+n-1 adeemajain answered Nov 11, 2018 adeemajain comment Share Follow See 1 comment See all 1 1 comment reply Lakshman Bhaiya commented Nov 14, 2018 reply Follow Share @ Vipin Rai why you select this is the best answer? Hemanth_13 already explain in the comment section. please remove, this is not a good answer. If she explains better than anyone then you can select the best answer. 0 votes 0 votes Please log in or register to add a comment.