Question $5.$ Exercise $2\mathrm{.}19$ from DPV$.$ You may get significant partial credit for a good verbal

explanation of your improved algorithm, but give clear, parseable pseudocode for full credit. In

particular, your solution must be a divide$-$and$-$conquer one. State and justify the runtime of both

algorithms to argue that your solution is superior.

$2\mathrm{.}19.$ A $k-$way merge operation. Suppose you have $k$ sorted arrays, each with $n$ elements, and you want

to combine them into a single sorted array of $kn$ elements.

$($a$)$ Here's one strategy: Using the merge procedure from Section $2\mathrm{.}3,$ merge the first two ar$-$

rays, then merge in the third, then merge in the fourth, and so on$.$ What is the time

complexity of this algorithm, in terms of $k$ and $n?$

$($b$)$ Give a more efficient solution to this problem, using divide$-$and$-$conquer.