In this article, we have explored 3 approaches to merge K sorted arrays such that the resulting array is sorted as well. This involve the concept of Min / Max Heap.

Table of contents:

1. Problem Statement
2. Approach 1 : Naive Approach
3. Approach 2: Using merging
4. Approach 3: Using Min-Heap

Pre-requisite: Min/ Max Heap

Problem Statement

Given K no. of sorted arrays of size N each, merge and sort them, print the sorted output.

Example

Input:

3 4
1 4 7 10
2 5 8 11
3 6 9 12

Output:

1 2 3 4 5 6 7 8 9 10 11 12

Solution

Approach 1 : Naive Approach

The basic idea behind this approach is to iterate through each array and keep track of the current element in each array, then add the smallest element to the final result array. This process is repeated until all elements have been added to the final result array.

This process is as follows:

• First, initialize a array of size N * K.
• Then, for each array in the input, we create a pointer to keep track of the current element in that array.
• We then iterate through each array and compare the current element at the pointer for each array.
• The smallest element is added to the final result array, and the pointer for the array with the smallest element is incremented.

This process is repeated until all elements have been added to the final result array.

Implementation

Implementation of naive approach in java:

public class Main {
    public static int[] merge(int[][] arrays) {
        int k = arrays.length;
        int n = arrays[0].length;
        
        // Initialize the result array
        int[] result = new int[k * n];
        
        // Create an array to keep track of the current element for each input array
        int[] pointer = new int[k];
        
        // Initialize the result array index
        int index = 0;
        
        // Repeat until all elements have been added to the final result array
        while (index < k * n) {
            int min = Integer.MAX_VALUE;
            int minArray = -1;
            
            // Find the array with the smallest current element
            for (int i = 0; i < k; i++) {
                if (pointer[i] < n && arrays[i][pointer[i]] < min) {
                    min = arrays[i][pointer[i]];
                    minArray = i;
                }
            }
            
            // Add the smallest element to the final result array
            result[index++] = min;
            pointer[minArray]++;
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int K = s.nextInt();
        int N = s.nextInt();
        int arr[][] = new int[k][n];
        for(int i=0,; i<k; i++) {
            for(int j=0; j<n; j++) {
                arr[i][j] = s.nextInt();
            }
        }
        
        int[] result = merge(arr);
        
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

• Below Image shows the representation of naive approach
  

Step by Step Guide to use naive approach

1. Initialize an empty array called result to store the final merged and sorted array.
2. Create an array called pointers of size K to keep track of the current index of each input array. Initialize each element to 0.
3. Create a variable size to store the total number of elements in all the input arrays.
4. Create a while loop that continues until size is equal to the number of elements added to the final result array.
5. Inside the while loop, initialize a variable min to a very large value (e.g. Integer.MAX_VALUE) and a variable minArray to -1.
6. Use a for loop to iterate through each input array. In each iteration, check if the current pointer index is less than N and if the current element in the array is less than min.
7. If the current element is smaller than min, update min to the current element and minArray to the current array index.
8. After the for loop, add the value of min to the result array and increment the pointer index of the array at index minArray by 1.
9. Also, increment the size variable by 1.
10. Repeat steps 4 to 9 until size is equal to the total number of elements in all input arrays.
11. Return the result array.

Complexity Analysis

Time complexity: O(N * K^2)

• In each iteration, we also compare the current element at the pointer for each array, which take O(K) time.
• So the overall time complexity becomes O(K * N * K).

Space Complexity: O(N * K)

• we are using an additional array of size O(N * K) to store the final result.

Approach 2: Using merging

The basic idea behind this approach is to repeatedly merge pairs of arrays until we are left with a single merged and sorted array.

This process is as follows:

• The first step is to divide the K arrays into pairs and merge each pair using a merge sort-like approach.
• We can then take the resulting arrays and merge them again, continuing this process until we have a single merged and sorted array.

One key advantage of this approach is that it can be easily parallelized, allowing us to take advantage of multiple processors or threads to speed up the merge process.

Implementation

Implementation of merging approach in java:

public class Main {
    public static int[] merge(int[][] arrays) {
        int k = arrays.length;
        int n = arrays[0].length;

        // Initialize the result array
        int[] result = new int[k * n];

        // Repeat until we have a single merged array
        while (k > 1) {
            int index = 0;
            for (int i = 0; i < k; i += 2) {
                int[] left = arrays[i];
                int[] right = i + 1 < k ? arrays[i + 1] : new int[0];
                arrays[index++] = mergeTwoArrays(left, right);
            }
            k = (k + 1) / 2;
        }

        return arrays[0];
    }

    // Helper method to merge two sorted arrays
    public static int[] mergeTwoArrays(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }

        while (i < left.length) {
            result[k++] = left[i++];
        }

        while (j < right.length) {
            result[k++] = right[j++];
        }

        return result;
    }

    public static void main(String[] args) {
        int K = s.nextInt();
        int N = s.nextInt();
        int arr[][] = new int[k][n];
        for(int i=0,; i<k; i++) {
            for(int j=0; j<n; j++) {
                arr[i][j] = s.nextInt();
            }
        }

        int[] result = merge(arr);

        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

• Below Image shows the representation of merging approach

Complexity Analysis

Time Complexity: O(N * K * log(K))

• The time complexity of this algorithm is O(N * K * log(K)), where N is the size of each array and K is the number of arrays.
  Space Complexity: O(N * K)
• we are using an additional array of size O(N * K) to store the final result.

Approach 3: Using Min-Heap

The basic idea behind using a min heap is that we can insert the first element from each of the K arrays into the heap and then repeatedly extract the minimum element from the heap and add it to the final sorted array. After extracting an element from the heap, we then insert the next element from the same array into the heap, ensuring that the heap always contains the smallest element from each of the K arrays.

This process is as follows:

• First we create a min heap with a size of K and insert the first element from each of the K arrays into the heap.
• We then repeatedly extract the minimum element from the heap and add it to the final sorted array.
• After extracting an element from the heap, we then insert the next element from the same array into the heap, ensuring that the heap always contains the smallest element from each of the K arrays.

Implementation

Implementation of Min-heap approach in java:

import java.util.PriorityQueue;

public class Main {
    public static int[] merge(int[][] arrays) {
        // Create a min heap with a size of K
        PriorityQueue<ArrayContainer> heap = new PriorityQueue<ArrayContainer>(arrays.length, (a, b) -> a.array[a.index] - b.array[b.index]);

        // Insert the first element from each of the K arrays into the heap
        for (int i = 0; i < arrays.length; i++) {
            heap.offer(new ArrayContainer(arrays[i], 0));
        }

        // Create a final array to store the merged elements
        int[] result = new int[arrays.length * arrays[0].length];
        int index = 0;

        // Repeat until the heap is empty
        while (!heap.isEmpty()) {
            // Extract the minimum element from the heap and add it to the final array
            ArrayContainer ac = heap.poll();
            result[index++] = ac.array[ac.index];

            // Insert the next element from the same array into the heap
            if (ac.index < ac.array.length - 1) {
                heap.offer(new ArrayContainer(ac.array, ac.index + 1));
            }
        }

        return result;
    }

    // Helper class to store array and current index
    static class ArrayContainer {
        int[] array;
        int index;

        ArrayContainer(int[] array, int index) {
            this.array = array;
            this.index = index;
        }
    }

    public static void main(String[] args) {
        int K = s.nextInt();
        int N = s.nextInt();
        int arr[][] = new int[k][n];
        for(int i=0,; i<k; i++) {
            for(int j=0; j<n; j++) {
                arr[i][j] = s.nextInt();
            }
        }

        int[] result = merge(arr);

        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

• Below Image shows the representation of min-heap approach
  

and so on.

Explanation

• In this example, the merge() method takes in a 2D array of integers called arrays and returns the merged and sorted array.
• The ArrayContainer class is a helper class which is used to store the array and current index. This is used to extract the next element from the same array after the current element has been extracted from the heap.

Step by Step Guide to use min-heap approach

1. Initialize an empty array called result to store the final merged and sorted array.
2. Create a min-heap of size K to store the current element of each input array.
3. Use a for loop to iterate through each input array and add the first element of each array to the min-heap.
4. Create a while loop that continues until the min-heap is empty.
   5 Inside the while loop, remove the minimum element from the min-heap and add it to the result array.
5. Check if the input array from which the minimum element was removed has any more elements. If it does, add the next element to the min-heap.
6. Repeat steps 4-6 until the min-heap is empty.
7. Return the result array

Complexity Analysis

Time Complexity: O(N * K * log(K)),

• where N is the size of each array and K is the number of arrays.

Space Complexity: O(K)

• as we only need to store the elements in the heap at any given time. or O(N * K) if we want to store it in a output array.

With this article at OpenGenus, you must have the complete idea of solving this problem of merging K sorted arrays.