Solution Review: Merge a Number of Sorted Arrays

This review discusses the solution of the Merge Sorted Arrays challenge in detail.

Solution # 1

A naive solution to this problem is to append all the k arrays one after another in the output (Nk)(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(Nk)O(N*k). Since std::sort() runs in O(log(size))O(log(size)) and the size of the output array is (Nk)(N*k), sorting would take O(log(Nk))O(log(N * k)). The total time complexity of this naive solution would thus be O(Nklog(Nk))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.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.