Design algorithms for the following problem using divide and conquer paradigm. Please provide well described and correct algorithm.

Dividing the problem into sub problems

Solving sub problems

Merging solutions of sub problems.

Give an algorithm that gets k sorted arrays (of integers) each of size n as input, and merges them into a single sorted array.

Your grade depends on the run time of your algorithm. Your algorithm must clearly and precisely describe each of these three steps. Derive a recurrence relation for the run of the algorithm, and solve the recurrence relation.