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

**Example :**

int[][] A =newint[5][]; A[0] =newint[] { 1, 5, 8, 9 }; A[1] =newint[] { 2, 3, 7, 10 }; A[2] =newint[] { 4, 6, 11, 15 }; A[3] =newint[] { 9, 14, 16, 19 }; A[4] =newint[] { 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.

**Complete Code:**

**Output**:

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

Great Code ! However, I didn’t understand few things here.

1. Why are you starting at heap location 1 instead of 0.

2. During the initialization you are basically inserting the first element of every array into the heap. You will never come across ptrs[i] > n. Because you initialized ptrs[i] to be zero.

1. We start with heap location 1 because ,

For any given node at position i:

– Its Left Child is at [2*i] if available.

– Its Right Child is at [2*i+1] if available.

So “i” cannot be 0. Read this link for more information.

http://algorithms.tutorialhorizon.com/binary-min-max-heap/

2. ptrs[] start with 0 and goes till n-1. So when it becomes n, we will set the value as

Integer.max so it will never become greater than n.

You can start with 0-based index too. In that case, Left child would be 2i+1 and Right Child would be 2i+2