Given k sorted arrays of size n each, merge them and print the sorted output.

Input:
k = 3, n = 4
arr[][] = {
{1, 3, 5, 7},
{2, 4, 6, 8},
{0, 9, 10, 11}
} ;
Output: 0 1 2 3 4 5 6 7 8 9 10 11
Explanation: The output array is a sorted array that contains all the elements of the input matrix.

Approach

We think of the Merge operation in the Merge Sort to merge two sorted arrays into one. We can optimize this approach by merging in the pair and merge till it converges to a single array.

We can also use the Min Heap method to sort batches of k elements repeating n times. This will reduce the Space complexity to O(k)

The below problem approach might consists of minor coding issues that are resolved in the implementation in the end.

The below implementation consists of a Min Heap implementation.

You've successfully subscribed to Coding Today

Great! Next, complete checkout for full access to Coding Today

Welcome back! You've successfully signed in.

Unable to sign you in. Please try again.

Success! Your account is fully activated, you now have access to all content.