Merge Sort $[12$ points$]$

$1.$ Suppose a$[1$ : m$]$ and b$[1$ : n$]$ both contain sorted elements in non$-$decreasing order. Write an algorithm

that merges these items into c$[1$ : m $+$ n$].$ Your algorithm should be shorter than algorithm Merge

$($Slide $10,$ Lecture $11)$ since you can now place a large value in a$[$m $+1]$ and b$[$n $+1].[4$ points$]$

$2.$ The sequences X$1,$ X$2,...,$ X$$ are sorted sequences such that P$$

i$=1|$Xi$|=$ n$.$ Show how to merge these

$$ sequences in time O$($n log $).[8$ points$]$