Solution Review: Merge a Number of Sorted Arrays

Solution # 1

A naive solution to this problem is to append all the k arrays one after another in the output $(N*k)$ array and sort the output array using the std:: sort() function.

Time Complexity

Appending k sorted arrays into one output array would take $O(N*k)$. Since std::sort() runs in $O(log(size))$ and the size of the output array is $(N*k)$, sorting would take $O(log(N * k))$. The total time complexity of this naive solution would thus be $O(N*k * log(N*k))$.

Solution # 2 (Efficient)

The divide and conquer approach to this problem emerges when we start looking at the k arrays as the intermediate state of the merge sort algorithm. In other words, k sorted arrays in the merge sort algorithm wait to be merged into a bigger, merged, and sorted array.