Merge k sorted arrays

Merge k sorted arrays

Given k sorted arrays each having n elements, merge k sorted arrays into one n*k element array in sorted order. For example, given 3 arrays are as below

merge k sorted arrays
merge k sorted arrays

Result array should be like

Merge k sorted arrays

Merge k sorted arrays

Since all the input arrays are sorted, the first element in result array will be among the first elements of input arrays. How can we find the minimum among all the elements plucked from the first index of each array ? Easy, take those k elements (there are k arrays, so k first elements) and build a min heap. The root of the min heap the least element among the first elements of all arrays, so it will be the first element in the result array.

Once, we add the first element into the result array, we have to find the second element. Second element can be from the set of first elements of all input arrays except one array from which the first element of result array was added. So, we will take second element of that array.

In order to know which array gave the minimum element at a particular time, we will store additional information of about array and index at which minimum element was.

If i represents the array number, and j represents the index of the minimum number in heap in ith array, then we add (j+1)th element to the min heap next and re-heapify. If j goes out of bound for ith array, we take min heap with k-1 size and go on, till we have no elements left in heap.

Follow the procedure for (n-1)*k times. When all array elements are processed, result array will be in the sorted array.

Merge k sorted arrays: algorithm

  • Build min heap with the first element of all k arrays.
  • Pick the root of min element and put it in the result array.
  • If there are remaining elements in the array,  put next element at the root of min heap and heapify again
  • If all elements are already of an array are processed, reduce the size of min heap by 1.
  • Repeat step 2, 3 and 4 till min heap is empty.

Merge k sorted arrays: implementation

package com.company;

import java.util.PriorityQueue;

/**
 * Created by sangar on 2.12.18.
 */
public class MergeKSortedArrays {
    private class HeapNode{
        public int arrayNum;
        public int index;
        public int value;

        public HeapNode(int arrayNum, int index, int value){
            this.arrayNum = arrayNum;
            this.index = index;
            this.value = value;
        }
    }

    public int [] mergeKSortedArrays(int[][] arrays){

        if(arrays == null) return null;

        PriorityQueue<HeapNode> minHeap =
			new PriorityQueue<>(arrays.length,
                (HeapNode a,HeapNode b)-> a.value - b.value);

        int size = 0;
        for(int i =0; i<arrays.length; i++){
            size += arrays[i].length;
        }
        int[] result = new int[size]; // k * n

        //add first elements in the array to this heap
        for(int i=0; i<arrays.length; i++){
            minHeap.add(new HeapNode(i, 0, arrays[i][0]));
        }

        //Complexity O(n * k * log k)
        for(int i=0; i< size; i++){
            //Take the minimum value and put into result
            HeapNode node = minHeap.poll();

            if(node != null){
                result[i] = node.value;
                if(node.index + 1 < arrays[node.arrayNum].length) {
                    //Complexity of O(log k)
                    minHeap.add(new HeapNode(node.arrayNum,
                           node.index + 1,
                           arrays[node.arrayNum][node.index + 1]));
                }
            }
        }
        return result;
    }
}

Test cases

package test;

import com.company.MergeKSortedArrays;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class MergeKSortedArraysTest {

    MergeKSortedArrays tester = new MergeKSortedArrays();

    @Test
    public void mergeKSortedArraysTest() {

        int[][] input  ={
            { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }
        };

        int[] expectedOutput = {1,2,3,4,5,6,7,8,9,10,11,12};

        int [] output = tester.mergeKSortedArrays(input);

        System.out.println(Arrays.toString(output));
        assertEquals(Arrays.toString(expectedOutput), 
					Arrays.toString(output));
    }

    @Test
    public void mergeKSortedArraysWithUnequalSizeTest() {

        int[][] input  ={
                { 1, 2 }, { 5, 6, 7}, { 9, 10, 11, 12 }
        };

        int[] expectedOutput = {1,2,5,6,7,9,10,11,12};

        int [] output = tester.mergeKSortedArrays(input);

        System.out.println(Arrays.toString(output));
        assertEquals(Arrays.toString(expectedOutput),
			Arrays.toString(output));
    }

    @Test
    public void mergeKSortedArraysWithNullTest() {

        int [] output = tester.mergeKSortedArrays(null);

        assertEquals(null, output);
    }
}

Complexity of code to merge k sorted arrays is O(n * k * log k) along with space complexity of O(k).

Please share if there is something wrong or missing. If you are preparing for an interview, please sign up to receive interview preparation kit for free.