why worst case comparatin for merging 2 sorted arrays into a third sorted array is n+m-1?

Question

I need a logical reason for this question

Answer 1

Let's first consider that after each comparison you take the smaller element and add it to the sorted array - with a three-way comparison you can take both elements in case of equality but it can only decrease the number of comparisons (and will change nothing if all elements are unequal). Second - we count only element comparisons, not index comparisons in loops (since they are different things it makes no sense to calculate them together)

Now each comparison reduces one of unsorted arrays by one. And the comparisons end when one of the arrays is empty (and the other has k >0 elements). So at start you have n+m elements in both arrays, then you doing n+m-k comparisons getting k elements in both arrays. Since the smallest possible k is 1 the worst case is n+m-1 comparisons

For this approach to be a strict proof (not just a "logical reason") you have to provide an example when n+m-1 comparisons are needed.