**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 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 lists and create HeapNode object and insert it into min-Heap.
- Extract the minimum Node from the min-Heap, 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 min-Heap.
- If at any point in time any list gets over, insert +∞ into min-Heap.
- 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]