# Question: suppose we have a subroutine merge2 to merge two sorted...

###### Question details

Suppose we have a subroutine merge2 to merge two sorted arrays
in linear time ((kn)). The purpose is to design a divide and
conquer algorithm (Alg2) to

merge k sorted arrays using merge2 recursively.

a) Write a pseudocode for Alg2.

(Hint: Assume that the input is given in a (k x n) array with the
rows and columns sorted in ascending order)

b) Write the running time of Alg2 as a recurence relation. T(k) =?

c) Construct a recursion tree with log k levels and (kn)
work per level to represent the

recurance relation obtained in part (b).

d) Since k is a constant, is Alg2 asymptotically faster than an
algorithm with running time

(n log
n)? why?

Please give a detailed answer for all the parts as I'm trying to understand how to solve these problems.