Merge K Sorted Arrays

Last updated: 29th Aug, 2020

Problem Statment

Given K sorted arrays each with N elements merge them and output the sorted array.
First line contains 2 space separated integers K and N. Next lines contain K*N space separated integers

Elements of array <= |10^15| N <= 10^5 K <= 10

Input Format
3 4
1 3 5 7 2 4 6 8 0 9 10 11

Output Format
0 1 2 3 4 5 6 7 8 9 10 11

Explanation
If we were to combine all the arrays into one and then sort it , the output would be as above.

Approach:

This problem can be done easily by using priority queue. 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.

C++ Code

#define ll long long int

typedef pair<int,pair<int,int>>node;

int main()
{
	ll k,n;
	cin>>k>>n;
	ll v[k][n];
	vector<int>result;
	for(ll i=0;i<k;i++)
	{
		for(ll j=0;j<n;j++)
		{
		cin>>v[i][j];
		}
	}
	priority_queue <node, vector<node>, greater<node>> g;
	for(ll i=0;i<k;i++)// for the first three elements
	{
		g.push({v[i][0],{i,0}});
	}

	while(g.size()>0)
	{
		node curr=g.top();
		ll value=curr.first;
		ll x=curr.second.first;
		ll y=curr.second.second;
	    result.push_back(value);
		g.pop();
		if(y+1<n)
		{
			g.push({v[x][y+1],{x,y+1}});
		}

	}
	for(ll i=0;i<result.size();i++)
	{
		cout<<result[i]<<" ";
	}
	cout<<endl;
}