Be the first user to complete this post

Add to List 
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 a result[] of size n*k.
 Copy all the elements from k arrays into the result array. This will take O(nk).
 Sort the result[] using Merge Sort. This will take O(nkLognk) time.
Better Approach: O(nkLogk)
 Create a result[] of size n*k.
 Create MinHeap 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 lists and create HeapNode object and insert it into minHeap.
 Extract the minimum Node from the minHeap, and insert the data into the result array.
 The extracted node will also contain the list to which it belongs, insert the next element from that list into minHeap.
 If at any point in time any list gets over, insert +∞ into minHeap.
 Keep repeating until all the K list gets over.
See the animation below for a better understanding.
Complete Code:
Code:
[1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 14, 15, 16, 19]
Also Read: