Merge K Sorted Arrays

Q: What is a Sorted Array?

An array is a collection of elements stored in continuous storage blocks in the memory. Sorting in programming refers to placing the elements of a data structure in a specific and meaningful manner. Sorting is an essential part of data processing. Efficient sorting algorithms are crucial so that we can perform operations that require sorted input optimally. Therefore, the array having elements in either increasing or decreasing order is known as a Sorted Array.

Q: 2. How are we handling the case of duplicate elements?

Let’s consider the Min Heap approach, we are removing minimum elements in every iteration so if duplicate elements are present in min-heap, the getMin() function will remove them one by one which will help to handle the case of duplicate elements.

Q: 3. What is Min Heap?

A Min-Heap is a complete binary tree, or we can just say a binary tree (which means each node can have a maximum of 2 children) in which each internal node has a value that is smaller than or equal to the values in the children node. We can store a heap in an array. If a node is stored at index ‘K’, then its left child is stored at index 2 * K + 1 and its right child at index 2 * K + 2.

Introduction

This blog will cover how to merge ‘K’ sorted arrays. Let’s start by looking at the problem statement. There are K Sorted Arrays, each of size N, and you have to merge all these arrays to make one sorted array and return the result.

Let’s understand the problem with an example. We are using ‘K’ as 3 in this problem, and we have to return one sorted array after merging all these arrays -

Input -

Brute Force Approach

Step 1. Create a resultant array of size N * K.

Step 2. Iterate all the arrays from start to end and insert all the elements in the resultant array.

Step 3. Sort and print the resultant array.

Java Solution

import java.io.*;
import java.util.*;

public class Solution {

  public static int[] mergeArrays(int[][] array, int n, int K)
{
  // 'temp' variable used for indexing
  int temp = 0;
  int[] res = new int[n * K];

  for (int i = 0; i < K; i++) {
  for (int j = 0; j < n; j++)

{
res[temp ++] = arr[i][j];

            }
}

  // Sorting 'res' array
Arrays.sort(res);
  return res;
}

  public static void main(String[] args)
{
  int[][] arrays = {{ 1, 4, 7},
{ 1, 3, 4},
{ 2, 8, 10 }};
  int K = 3;
  int n = 3;

  // Storing the returned arrays from the 'mergeArrays' function
  int[] res = mergeArrays(arrays, n, K, res );

System.out.println("Resultant Merged array is : ");

  // Printing all the elements after merging 'K' sorted arrays
  for (int a = 0; a < res.length; a++)
{

System.out.print(res[a] + " ");

}

}
}

Output:

Resultant Merged array is
1 1 2 3 4 4 7 8 10

Better Approach

In this approach, we merge arrays in pairs. After the first iteration of merging, we have K/2 arrays. After the second merge, we will have K/4 arrays and so on. We will use recursion to implement this approach for the merge K sorted arrays problem.

Step 1. Create a function that takes K arrays and returns the resultant array.

Step 2. Implement base condition: if the value of 'K' is 1 then return the array. If ‘K’ contains two, then merge the two arrays and return the array.

Step 3. If the value of K > 2, then divide the group of 'K' elements into equal half and recursively call the function for each of the halves.

Step 4. Print the resultant array.

Java Solution for Merge K sorted Arrays

import java.util.*;

public class Solution{

  public static void merge2Array(int arr1[], int arr2[], int n1,int n2, int arr3[])
{
  int i = 0, j = 0, k = 0;

  //Merging two arrays and storing them in 'arr3'
  while (i<n1 && j <n2)
{

  if (arr1[i] < arr2[j])

{
arr3[k++] = arr1[i++];

}
else

{
arr3[k++] = arr2[j++];

            }
}

  //Leftover elements from an array having size 'n1'
  while (i < n1)
{
arr3[k++] = arr1[i++];
}

  //Leftover elements from an array having size 'n2'
  while (j < n2)
{
arr3[k++] = arr2[j++];
}

}

  public static void mergeKSortedArrays(int arr[][], int i, int j, int res[], int n)
{

  if(i == j)
{
  for(int p = 0; p < n; p++)

{
res[p] = arr[i][p];

            }
  return;
}

  if(j - i == 1)
{
merge2Array(arr[i], arr[j], n, n, res);
  return;
}

  //Dividing all the elements in the array
  int [] output1 = new int[n*(((i + j) / 2) - i + 1)];
  int [] output2 = new int[n*(j - ((i + j) / 2))];

mergeKSortedArrays(arr, i, (i + j) / 2, output1);
mergeKSortedArrays(arr, (i + j) / 2 + 1, j, output2);

  //function call to merge all the arrays formed using divide calls

merge2Array(output1, output2, n * (((i + j) / 2) - i + 1), n * (j - ((i + j) / 2)), res);
}

  public static void main(String[] args)
{

  int arrays[][] = {{ 1, 4, 7},
{ 1, 3, 4},
{ 2, 8, 10 }};

  int K = arrays.length;
  int[] res = new int[arrays[0].length*K];

mergeKSortedArrays(arrays,0,arrays[0].length, res, res[0].length);

System.out.println("Resultant Merged array is : ");

// Printing the elements
for (int i = 0; i < res.length; i++)

{
System.out.print(res[i] + " " );

}

}
}

Output:

Resultant Merged array is
1 1 2 3 4 4 7 8 10

Complexity Analysis of merge K sorted arrays problem:

Time Complexity: O(N * K * log K) where ‘N’ is the size of arrays and ‘K’ is the total number of sorted arrays. Total levels are log(K) and each level is doing N * K work, so complexity is O(N * K * log K).

Space Complexity: O(N * K * log k) where ‘N’ is the size of arrays and ‘K’ is the total number of sorted arrays. O(N * K) space is being used at each level and total levels are log(K) which makes it O(N * K * log K).

Efficient Approach for Merge K sorted Arrays

Min Heap can be used to handle this merge K sorted arrays problem but first, let's understand what MinHeap is -

A Min-Heap is a complete binary tree, or we can say a binary tree in which the value contained by each internal node is smaller than or equal to the values in the children of that node. We can store a heap in an array. If a specific node is stored at index ‘K’ of the array, then the left child of that node is stored at index 2 * K + 1, and the right child of that node is stored at index 2 * K + 2.

This solution has the same time complexity, which is O(N * K * log K). But it works much better. This algorithm starts with creating a MinHeap and inserting the first element of all the 'K' arrays, then removing the root element of Min Heap and putting it in the resultant array named 'res' in the code and inserting the next element from the array of the removed elements. To get the result, we have to execute this step until there is no element left in Min Heap.

Algorithm for the efficient approach

Step 1. Create a min-heap following the definition mentioned above and insert the first element of 'K' arrays.

Step 2. Iterate until the MinHeap size > 0.

Step 3. Get the top element of the MinHeap and this top element is the minimum element and prints the element.

Step 4. Insert the next element from the same respective array from which the element was removed.

Step 5. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

Example:

Input:

Java Solution

class MinHeapNode
{
  int data;
  int i;
  int j;

  public MinHeapNode(int data, int i, int j)
{
  this.data = data;
  this.i = i;
  this.j = j;
}
};

class MinHeap
{
MinHeapNode[] heapArray;
  int size;

  public MinHeap(MinHeapNode a[], int size)
{
size = size;
heapArray = a;
  int i = (size - 1)/2;
  while (i >= 0)
{
MinHeapify(i);
i--;
}
}

  void MinHeapify(int i)
{
  int l = left(i);
  int r = right(i);

  int smallest = i;

  if (l < size && heapArray[l].data < heapArray[i].data)

{
smallest = l;

}

if (r < size && heapArray[r].data < heapArray[smallest].data)

{
smallest = r;

}

  if (smallest != i)
{
swapNode(heapArray, i, smallest);
MinHeapify(smallest);
}
}

  int left(int i) { return (2*i + 1); }

  int right(int i) { return (2*i + 2); }

MinHeapNode getMin()
{

        // Printing error message if ‘size’ is 0
  if(size <= 0)
{
System.out.println("Heap is empty");
  return null;
}

  return heapArray[0];
}

  void replaceMin(MinHeapNode root) {
heapArray[0] = root;
MinHeapify(0);
}

// Swapping the nodes
  void swapNode(MinHeapNode[] arr, int i, int j) {
MinHeapNode temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}



  public static void mergeKArrays(int[][] arr, int k)
{
MinHeapNode[] heapArray = new MinHeapNode[k];
  int finalSize = 0;

  for(int i = 0; i < arr.length; i++)
{
MinHeapNode node = new MinHeapNode(arr[i][0],i,1);
heapArray[i] = node;
finalSize += arr[i].length;
}

MinHeap mHeap = new MinHeap(heapArray, k);

        // ‘result’ is the resultant array
  int[] result = new int[finalSize];

  for(int i = 0; i < finalSize; i++)
{

MinHeapNode root = mHeap.getMin();
result[i] = root.data;

  if(root.j < arr[root.i].length)

{
root.data = arr[root.i][root.j++];

}
else

{
root.data = Integer.MAX_VALUE;

}

mHeap.replaceMin(root);
}

// Printing the resultant array
for(int i = 0 ; i < finalSize ; i++)

{
System.out.print(result[i] + " ");
}

        System.out.println();

}

  public static void main(String args[]){
  int[][] arr= {{ 1, 4, 7},
{ 1, 3, 4},
{ 2, 8, 10 }};
System.out.println("Resultant Merged array is :");
mergeKArrays(arr,arr.length);
}
};

Output:
Resultant Merged array is
1 1 2 3 4 4 7 8 10

Frequently Asked Questions

What is a Sorted Array?

An array is a collection of elements stored in continuous storage blocks in the memory. Sorting in programming refers to placing the elements of a data structure in a specific and meaningful manner. Sorting is an essential part of data processing. Efficient sorting algorithms are crucial so that we can perform operations that require sorted input optimally. Therefore, the array having elements in either increasing or decreasing order is known as a Sorted Array.

2. How are we handling the case of duplicate elements?

Let’s consider the Min Heap approach, we are removing minimum elements in every iteration so if duplicate elements are present in min-heap, the getMin() function will remove them one by one which will help to handle the case of duplicate elements.

3. What is Min Heap?