Number of Comparison in Worst Case of Merging Two Sorted Array?

Question

Given two sorted arrays A, B with size n and m. I am looking for worst number of comparison that merges these two arrays.

1) n+m-1

2) max(n,m)

3)min (m,n)

4) mn

I know this is not a good question because the merge algorithm not mentioned, but i think, The normal merge sort algorithm - merge step with normally apply n + m -1 comparisons, where one list is of size n and and the other list is of size m. Using this algorithm is the most simplest approach to combine two sorted lists. any expert could help me, am I right by choosing (1)?

Solution 1

This can easily be found out from the documentation:

Complexity

At most std::distance(first1, last1) + std::distance(first2, last2) - 1 comparisons.

So No. 1 it is. (Yes it assumes that the standard committee got the complexity right, but that is not a stretch.)

Option 4 is obviously false because n + m - 1 grows slower than n*m, so we already have a better estimate.

Option 3 is false with this counterexample:

[4], [1, 2, 6, 7]

needs at least two comparisons. Option 2 counterexample:

[1,6], [2,5]

would need 3 comparisons:

1 < 2?, 6 < 2?, 6 < 5?

Solution 2

Assuming m < n, at least m comparisons and at most n+m-1 comparisons (worst case). So assuming all elements of the smallest list come first, the minimum number of comparisons is min (n, m). Assuming that by simplest you mean best case, then answer 3 is the correct answer. Answer 1 is correct for the worst case.

Comments

[Admin]

is it possible add more detail ?

[Baum mit Augen]

@Prof.KosiNoura Are you looking for a mathematical proof for the complexity? I do not think this is on-topic here. (Although probably not hard.)

[Admin]

no, for example why mn is not correct? the algorithm not mentined !!

[Admin]

"Option 4 is obviously false because n + m - 1 grows slower than n*m, so it already is a better estimate." why if slower, not better estimate?

[Baum mit Augen]

@Prof.KosiNoura What? n+m-1 is already a worst case estimate and n+m-1 <= n*m for positive integers (That you should be able to work out on your own). So n*m cannot be the correct estimate because we already found a better upper bound. I hope that clarifies, I do not understand your comment at all.