Recall that the merge operation $($from the Merge sort$)$ that merges two sorted arrays A

and B

requires time $\backslash$Theta $(|$A$|+|$B$|)$

$,$ where $|$A$|$

$($resp$.|$B$|$

$)$ denotes the length of A

$($resp$.$ B

$).$

Suppose you are given k

sorted arrays A$1,$A$2,...,$Ak

$,$ each having n

elements, and the problem is to merge the k

arrays into a single sorted array of length kn

$.$

A very simple approach for solving this problem is to use the merge operation as follows: merge the first two arrays, then merge in the third array, then merge in the fourth array, and so on$.$

Answer the following questions:

What is the running time of the approach taken above. Give your answer in terms of both k

and n

$.$

Give a more efficient solution $($using pseudocode$)$ to this merging problem using divide$-$and$-$conquer? illustrate how your solution works using an example for k$=8$

$($drawing a picture is useful$).$ Give the running time in terms of k

and n

$.$