If there doesn't exist any other element at the list, what do we do?

[evinda]

Hello! (Wave)

I want to write a $O(n \lg k)$ time algorithm in order to merge $k$ sorted lists into one sorted list, where $n$ is the total number of the elements in all the input lists.

I tried the following:

We create an array with k elements, where $A$ is the firstunused element of the ith list.We create a $k$-sized heap and we put in the heap the first elements of the $k$ lists. Then we repeat the following steps, while the heap isn't empty.
1. Minheapify
2. Delete the root of the heap and put it in the output list.
3. Put in $A[1]$ the last element of the corresponding list, if it exists.

Is it right? At $3$, if there doesn't exist any other element at the list, what do we do?

 

[Future Bruno]

Yes, your algorithm is correct. At step 3, if there doesn't exist any other element at the list, do nothing. The heap will eventually become empty as all elements from the lists have been added to the output list.