Problem $4.$ Recall the Mergesort algorithm, You are given $k$ sorted arrays, each containing $n$ elements. The goal

is to merge them into one sorted array containing $kn$ elements. We will explore two methods to achieve this and

analyze their time complexities:

Sequential Merge Strategy:

$($a$)$ Merging Two Arrays: To begin, consider merging two sorted arrays using a standard merge procedure

$($like in merge sort$),$ which takes linear time based on the total size of the arrays. Hint: What is the

time complexity of merging two arrays of size $n?$

$($b$)$ Merging Multiple Arrays Sequentially: Next, merge the first two arrays. After obtaining the

merged result, merge the third array into it$,$ and continue this process until all arrays are merged. Hint:

After merging the first two arrays $($size $2n),$ the next merge involves $3n$ elements. How does the size

increase after each step?

Using Divide$-$and$-$Conquer:

$($a$)$ Divide the Arrays: Rather than merging arrays one by one, consider dividing the $k$ arrays into pairs

and merging them simultaneously. Hint: This divide$-$and$-$conquer strategy is similar to mergesort. If

you merge half the arrays at each level, how many levels will there be$?$

$($b$)$ Merge Two Arrays at Each Level: At each level, merge two arrays $($or merged subarrays$)$ of size

$n$ from the previous step. The total number of elements at each level remains $kn,$ but how many levels

are there? Hint: The number of levels corresponds to $logk.$

Which approach is more efficient, and why? Think about how divide$-$and$-$conquer helps reduce the time

complexity when handling large datasets.