Question

You are given an input of k arrays each of size n. Each one of the k arrays is sorted. Give an algorithm that turns the k sorted arrays into one sorted array of k * n elements.

Please explain the algorithm in words and analyze the run time.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

An efficient solution is to use heap data structure. The time complexity of heap based solution is O(N Log k).

1. Create an output array.
2. Create a min heap of size k and insert 1st element in all the arrays into the heap
3. Repeat following steps while priority queue is not empty.
…..a) Remove minimum element from heap (minimum is always at root) and store it in output array.
…..b) Insert next element from the array from which the element is extracted. If the array doesn’t have any more elements, then do nothing.

Kindly revert for any queries

Thanks.