Merge K Sorted Arrays and Print Sorted Output

Problem Statement

In the “Merge K Sorted Arrays and Print Sorted Output” problem we have given k sorted arrays of different size. Write a program to merge those arrays and prints the final sorted array as output.

Input Format

The first line containing an integer n.

Next n lines containing an integer x then x space separated integers.

Output Format

The first and only one line containing final array which formed by merging all the arrays.

Constraints

• 1<=n<=10^5
• Sum of size of all the arrays will be less than 10^5
• 1<=s[i]<=10^9

Example

3
3 1 2 3
4 3 4 5 6
2 8 9

1 2 3 3 4 5 6 8 9

Explanation: First we merge starting 2 arrays then output array after merging is 1, 2, 3, 3, 4, 5, 6. Now we merge 3rd array to this array. So, our final updated array is 1, 2, 3, 3, 4, 5, 6, 8, 9.

Algorithm

An optimal solution will be to take pairs of arrays at each step. Then merge the pairs using the two pointer technique of merging two sorted arrays. Thus, after merging all the pairs, the number of arrays will reduce by half. We, will continue this till the number of remaining arrays doesn’t become 1. Thus, the number of steps required will be of the order log(k) and since at each step, we are taking O(S) time to perform the merge operations, the total time complexity of this approach becomes O(S * log(k)).

1. Create an output array of size “sum of size of all the arrays”.

2. Create a min-heap of size k and insert the first element in all the arrays into the min-heap.

3. Initialize count = 0 and till count less than n*k.

1. Get the minimum element from the heap(ie, root) and store it in the output array ie, output[count]
2. Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

4. Print the output array.

Implementation

C++ Program to Merge K Sorted Arrays and Print Sorted Output

#include <bits/stdc++.h> 
using namespace std; 

vector<int> mergeTwoArrays(vector<int> l, vector<int> r) 
{
  vector<int> ret; 
  int l_in = 0, r_in = 0; 
  while (l_in + r_in < l.size() + r.size()) 
  { 
    if (l_in != l.size() && (r_in == r.size() || l[l_in] < r[r_in])) 
    { 
      ret.push_back(l[l_in]); 
      l_in++; 
    } 
    else 
    { 
      ret.push_back(r[r_in]); 
      r_in++; 
    } 
  } 
  return ret; 
} 

vector<int> mergeArrays(vector<vector<int> > arr) 
{ 
  vector<vector<int> > arr_s; 
  while(arr.size() != 1) 
  { 
    arr_s.clear(); 
    for (int i = 0; i < arr.size(); i += 2) 
    { 
      if (i == arr.size() - 1) 
        arr_s.push_back(arr[i]); 
      else
        arr_s.push_back(mergeTwoArrays(arr[i],arr[i + 1])); 
    } 
    arr = arr_s; 
  } 
  return arr[0]; 
} 

int main() 
{ 
    int n;
    cin>>n;
    vector<vector<int>> v;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        vector<int> temp;
        for(int j=0;j<x;j++)
        {
            int p;
            cin>>p;
            temp.push_back(p);
        }
        v.push_back(temp);
    }
  vector<int>output = mergeArrays(v); 
  for(auto u: output)
  {
      cout<<u<<" ";
  }
  cout<<endl;
  return 0; 
} 

Java Program to Merge K Sorted Arrays and Print Sorted Output

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static ArrayList<Integer> mergeTwoArrays(ArrayList<Integer>  l, ArrayList<Integer>  r) 
    {
  ArrayList<Integer>  ret = new ArrayList<Integer>(); 
  int l_in = 0, r_in = 0; 
  while (l_in + r_in < l.size() + r.size()) 
  { 
    if (l_in != l.size() && (r_in == r.size() || l.get(l_in) < r.get(r_in))) 
    { 
      ret.add(l.get(l_in)); 
      l_in++; 
    } 
    else 
    { 
      ret.add(r.get(r_in)); 
      r_in++; 
    } 
  } 
  return ret; 
    }
    public static void mergeArrays(ArrayList<ArrayList<Integer> > arr)
    {
        int n = arr.size();
        ArrayList<ArrayList<Integer> >  arr_s = new ArrayList<ArrayList<Integer> >(); 
  while(arr.size() != 1) 
  { 
    arr_s.clear(); 
    for (int i = 0; i < arr.size(); i += 2) 
    { 
      if(i == arr.size() - 1) 
        arr_s.add(arr.get(i)); 
      else
        arr_s.add(mergeTwoArrays(arr.get(i), arr.get(i + 1))); 
    } 
    arr = arr_s; 
  } 
  for(int i = 0; i < arr.get(0).size(); i++) 
        { 
            System.out.print(arr.get(0).get(i) + " ");  
        }
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        ArrayList<ArrayList<Integer> > v =  new ArrayList<ArrayList<Integer> >();
        for(int i=0;i<n;i++)
        {
            int x = sr.nextInt();
            ArrayList<Integer> temp = new ArrayList<Integer>();
            for(int j=0;j<x;j++)
            {
                int p = sr.nextInt();
                temp.add(p);
            }
            v.add(temp);
        }
        mergeArrays(v);
        System.out.println();
    }
}

2
3 1 2 7
4 5 6 8 9

1 2 5 6 7 8 9

Complexity Analysis to Merge K Sorted Arrays and Print Sorted Output

Time Complexity

O(s*logk) where s is denoting the sum of size of the all arrays. And n is denoting the number of arrays.

Space Complexity

O(s) where s is denoting the sum of size of the all arrays. Here we use this space to store the final answer.