Merge K Sorted Arrays

Objective: Given k sorted array, write an algorithm to merge Them into One sorted array.

Example :

int[][] A = new int[5][];

A[0] = new int[] { 1, 5, 8, 9 };
A[1] = new int[] { 2, 3, 7, 10 };
A[2] = new int[] { 4, 6, 11, 15 };
A[3] = new int[] { 9, 14, 16, 19 };
A[4] = new int[] { 2, 4, 6, 9 };

Output:
[1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 14, 15, 16, 19]

Naive Solution: O(nkLognk)

  • Create an result[] of size n*k.
  • Copy all the elements from k arrays into result array. This will take O(nk).
  • Sort the result[] using Merge Sort. This will take O(nkLognk) time.

Better Approach: O(nkLogk)

  • Create an result[] of size n*k.
  • Create Min-Heap of type HeapNode.( HeapNode- Every Node will store the data and the list no from which it belongs).
  • Now take one element from each of the K list and create HeapNode object and insert into min-Heap.
  • Extract the minimum Node from the min-Heap, insert the data into result array.
  • The extracted node will also contain the list to which it belongs, insert the next element from that list into min-Heap.
  • If any point of time any list gets over, insert +∞ into min-Heap.
  • Keep repeating until all the K list gets over.

See the animation below for better understanding.

 
1/17
2/17
3/17
4/17
5/17
6/17
7/17
8/17
9/17
10/17
11/17
12/17
13/17
14/17
15/17
16/17
17/17
previous arrow
PlayPause
next arrow
Complete Code:
https://gist.github.com/thmain/388c17200e10dab61a5a

Output:

[1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 14, 15, 16, 19]