merge sort

Question

Answer 1

we have 4 sorted list each of 8 element(keys)
1 list .
2 list
3 list
4 list
now  to merge  first  two list i.e.

 list 1 list 2 we need (m+n-1) comparison  =15..........................LIST A(16 element)

 list 3 list 4 we need (m+n-1) comparison  =15........................... LIST B(16 element)
 now to merge these two we require   (16+16-1)=31
total 15+15+31=61

Answer 2

isanswer 61?

Comments

Yes the answer is 61 but not able to get it how?

---

for this type of q u take randomly short arrays and try to come up with worst case

let A1 and A2 are two arrays of length m and n .let i points to 1st index of A1 and j points to 1st index of A2

let R be the result array

A1: 1, 2, 3  A2: 4,5, 6 when both are in ascending then apply merge sort

compare 1 and 4, since1<4 so increament i e.g i++ and copy 1 to result array

compare 2 and 4 , 2< 4 so i++, copy 2 to R

compare 3 and 4 , 3<4 so i++ copy 3 to R

now A1 is over so simply copy A2 in resultant array

this is best case of comparison which is min(m,n)

now letus take

A1: 1 6 8  and A2: 2 7

compare 1 and 2, copy 1 to R and i++

compare 6 and 2, copy 2 and j++

compare 6 and 7, copy 6 and i++

compare 8 and 7, copy 7 and j++

henre no of comparison = 4 which is m+n-1

hence in worst case we get m+n-1 no. of comparison for 2 sorted arrays of length m and n

here we have 4sorted list so

we get two arrays of 16 element by doing(8+8-1) = 15 comparison

no.of comaprison = 15*2 = 30

then these two sorted arrays are merged to give array of 31 element by doing (16+16-1) comparison = 31

hece total = 30+31

                 =61

hope u will get it!

---

Thanks for the explanation.

Answer 3

Number of comparisons requires : $nlogn-2^{^logn}+1$ (Formula)

so , substituting values in formal:

8*3-8+1=17.

since there are 4 lists : 4*17= 68.

And now it is mentioned in question that list is sorted so all (n-1) elements are sorted so we have to remove it from counting comparisons: 68-7= 61.

http://stackoverflow.com/questions/12346054/number-of-comparisons-in-merge-sort

Answer 4

Using the merge algorithm.. If one sorted list has m elements and another has n elements then it requires m+n-1 comparisons during merging of list in worst case...

There are four list of 8 elements.. First two list requires 8+8-1=15 comparison and another two list requires 8+8-1=15 comparison.. Now we have two list of 16 elements, the number of comparison required is 16+16-1=31 comparison..

Total we have 15*2+31=61 comparison