k$-$way merge operation is where you have k sorted arrays, each with n numbers sorted

in non$-$decreasing order, and you want to combine them into a single sorted array of kn

numbers. Note that both numbers, k and n$,$ can be arbitrarily large.

$($i$)$ 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$.$ Give an argument

showing what the asymptotic time complexity of this algorithm, in terms of k and n and

big$-$O notation, is$.[6$ marks$]$

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

Describe your algorithm precisely in words or by pseudocode. Give an argument show$-$

ing what its asymptotic time complexity in terms of k and n and big$-$O notation is$.$

$[4$ marks