Question $3$: Multi Merge

Consider the following slight variant of the Merge procedure we saw in class. The inputs are

two sorted arrays of integers, $B,C.$ Important technical note: As discussed in class, we

use the convention that accessing an out$-$of$-$bounds index returns $.$

$($a$)[2]$ If $B$ and $C$ are two arrays of not$-$necessarily$-$equal length, argue $($with $2-3$ lines of

reasoning$)$ that the Merge function takes time $O(|B|+|C|).$

$($b$)[5]$ Now suppose we are given $k$ sorted arrays $A_1,A_2,$dots,$A_k,$ each containing $n$ elements.

Consider the following procedure for merging all of them into one:

Define $S=\frac{O}{?}$

For $t=1,2,$dots,$k$ :

define Temp larrMerge$(S,A_t)$

set $S=$ Temp

Return $S$

Derive an expression $($in terms of $n,k)$ for the running time of the procedure above.