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.

Here is one strategy: Using the merge procedure from mergesort, merge the first two

arrays, 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?$

Give a more efficient solution to this problem, using divide$-$and$-$conquer.Given a sorted array of distinct integers $A[1,$dots,$n],$ you want to find out whether there is an

index i for which $A[i]=i.$ Give a divide$-$and$-$conquer algorithm that runs in time $O(nlogn).$