0 votes 0 votes explain how to solve the above question ! Algorithms algorithms sorting + – air1ankit asked Dec 11, 2018 air1ankit 496 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply parabol commented Dec 11, 2018 i reshown by parabol Dec 11, 2018 reply Follow Share Is the answer 64, if you follow external weighted path length method,then this is the answer 1 votes 1 votes Shubhgupta commented Dec 11, 2018 i edited by Shubhgupta Dec 11, 2018 reply Follow Share to merge two sorted list m+n-1 comparison is required so take 4 list 16,16,16,16 now see below 64 (32+32-1= 63 comparisons) / \ (16+16-1=31 comparisons) 32 32 (16+16-1= 31 comparisons) / \ / \ 16 16 16 16 total= 63+31+31 = 125 0 votes 0 votes air1ankit commented Dec 11, 2018 reply Follow Share the answer is 125 because the total number of comparison = ( n / 2 -1 ) + ( n / 2 - 1) = 2n -3 = 2 * 64 - 3 = 128 - 3 =125 (answer is given in solution ) 0 votes 0 votes parabol commented Dec 11, 2018 reply Follow Share I think its correct, if you use a similar function like 'merge' of mergesort, you only require comparisons one less than the total number of elements in the worst case. so,31+31+63=125 0 votes 0 votes air1ankit commented Dec 11, 2018 reply Follow Share total number of comparison = ( n / 2 -1 ) + ( n / 2 - 1) = 2n - 3 i am not getting this derivation ... can you please explain more 0 votes 0 votes parabol commented Dec 11, 2018 reply Follow Share For eg: consider a worst case input of 2 list. 1,3,5 and 2,4,6 - when we 'merge' them using merge function we only requires 5 comparisons(6-1) to form 1 2 3 4 5 6. In the main question ,lets name the 16 element sorted lists as A,B,C,D A and B are combined - 31 comparisons( 32-1) C and D -31 comparisons then AB and CD are combined (64-1 =63 comparisons) (AB and CD are combined list of 32 elements each). So total comparisons 31+31+63=125 Thats the logic I followed. I dont see how they are getting the value of '2n-3'. I am getting 'n-2' when I solve that equation, 0 votes 0 votes air1ankit commented Dec 11, 2018 reply Follow Share Got it ..! Thanks bro 1 votes 1 votes parabol commented Dec 11, 2018 reply Follow Share You are welcome :) 1 votes 1 votes Please log in or register to add a comment.