Divide-and-conquer algorithm for class

Question

We are starting to work with Divide and conquer algorithms in my Data structures class and I am having a lot of trouble completely understanding what I am supposed to do. Below is the which is basically asking for me to write a program that given k sorted arrays of size n, combine them using divide and conquer in a single array of size kn

The Problem: Supose that you have k sorted arrays of size n and wants to combine them in a single sorted array of size kn, write a pseudo-code with a efficient solution to this.

Is there any algorithm better then O(kn)??

Answer 1

Since all the arrays are sorted, you just need to compare and copy them into a single array, which can be done in O(kn).