#self doubt

Question

https://gateoverflow.in/1997/gate2014-2-38

for n inputs merge procedure takes n comparisons...how n-1 is used in this question...please explain!

Comments

If size of one array is m, and other is n, so we need to merge both the arrays to form an array of size m+n.

For filling each element of the new array of size (m+n), 1 comparison is needed (arrays need to be already sorted for merging).

So, according to me 'n' comparisons would be required if infinity is added to the end.

But, in the worst case if we don't follow the infinity convention, then the last element would not require comparison and can be put directly in the merged array. So, n-1 comparisons.

We are talking about optimal algorithm, so n-1 comparisons would be required.

---

@himgta

by adding infinity at each end

list 1: 5 6 7 8 (inf)

list 2: 1 2 3 4  (inf)

 

1 is compared with 5 ===> 1st comparission

2 is compared with 5 ===> 2nd comparission

3 is compared with 5 ===> 3rd comparission

4 is compared with 5 ===> 4th comparission

(inf) is compared with 5 ===> 5th comparission

(inf) is compared with 6 ===> 6th comparission

(inf) is compared with 7 ===> 7th comparission

(inf) is compared with 8 ===> 8th comparission

(inf) is compared with (inf) ==== stop ===> 9th comparission

But by doing this method, no.of comparissions increases by 2 ( due to two new elements added )

total elements = 4+4+2 ( for infinities ) = 10, ===> maximum comparissions = 9 which is m+n-1

---

now I got it...thanks bro@Shaik Masthan