Question

"3. When we have two sorted lists of numbers in non-descending order, and we need to merge them into one sorted list, we can simply compare the first two elements of the lists, extract the smaller one and attach it to the end of the new list, and repeat until one of the two original lists become empty, then we attach the remaining numbers to the end of the new list and it's done. This takes linear time. Now, try to give an algorithm using O(n log k) time to merge k sorted lists (you can also assume that they contain numbers in non-descending order) into one sorted list, where n is the total number of elements in all the input lists. Use a heap for k-way merging."

Answer 1

Answer:

Since we extract n elements in total, the algorithm for the running time for K sorted list is O (n log k+ k) = O (n log k)

Step-by-step explanation:

To understand better how we arrived at the aforementioned algorithm, we take it step by step

a, Construct a min-heap of the minimum elements from each of "k" lists.

The creation of this min-heap will cost O (k) time.

b) Next we run delete Minimum and move the minimum element to the output array.

Each extraction takes O (log k) time.

c) Then insert into the heap the next element from the list from which the element was extracted.

Now, we note that  since we extract n elements in total, the running time is

O (n log k+ k) = O (n log k).

So we can conclude that :

Since we extract n elements in total, the algorithm for the running time for K sorted list is O (n log k+ k) = O (n log k)