Merge 3 arrays in sorted order in C++

By Sakshi Gupta

In this tutorial, we will learn how to merge 3 arrays in sorted order in C++. Below is an interesting solution based on min-heap implemented by using a priority queue. For example-

Input:

3
-1 35 45
4
7 8 9 0
5
-23 -87 4 5 3

Output:

-87 -23 -1 0 3 4 5 7 8 9 35 45

How to merge 3 arrays in sorted order in C++

Basically, we will use a min-heap in our code. Heaps are a complete binary tree. In min-heap, the data present at the parent is less than it’s children node.

Push the elements of all the three arrays one by one in a min-heap. It gets stored in a tree-like this below:

We start printing from the top of min-heap and they get printed in sorted order.

Here, is the code implementation:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n1;
    cin>>n1;

    int a[100],b[100],c[100];

    for(int i=0;i<n1;i++)
    {
        cin>>a[i];
    }
    int n2;
    cin>>n2;

    for(int i=0;i<n2;i++)
    {
        cin>>b[i];
    }

    int n3;
    cin>>n3;

    for(int i=0;i<n3;i++)
    {
        cin>>c[i];
    }

   priority_queue<int,vector<int>,greater<int> > pq;

    for(int i=0;i<n1;i++)
    {
        pq.push(a[i]);
    }


    for(int i=0;i<n2;i++)
    {
        pq.push(b[i]);
    }

    for(int i=0;i<n3;i++)
    {
        pq.push(c[i]);
    }


   while(pq.empty()==false)
    {
        cout<<pq.top()<<" ";
        pq.pop();
    }


}

Here the Input is:

3
-1 35 45
4
7 8 9 0
5
-23 -87 4 5 3

And the Output is:

-87 -23 -1 0 3 4 5 7 8 9 35 45

Also, refer to:

Count the number of occurrences of an element in a linked list in C++

Time complexity: It will be o(m+n+k) where m,n, and k are sizes of the array as the arrays are only traversed once.