6.5-9

6.5-9 Give an O(n lg k)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a minheap for k-way merging.)
Solution:
1) pick first k elements from k sorted lists and form a MIN-HEAP (which takes $\theta(k log k)$ )
2) call MIN-HEAP-EXTRACT on the heap and extract the smallest of k sorted lists and insert in to final list. (which takes log k (since k is the no of elements) we do this for n elements.)
3) extract the next element from the same list whose element is placed in the final list and place it on the heap.

step 3 is to make sure we get all smaller values , compare and place on the final list. example:
List 1 : 1 2 5
List 2 : 4 5 6

step 1: pick k elements : (1, 4) is the min tree
step 2:call MIN-HEAP-EXTRACT returns 1 and place it on final list final list : (1)
step 3: we will extract 2 from list 1 and place it on the heap(4,2). This will make sure we return the smallest values of K lists.
we have to repeat step 1 for n/k elements hence the runnning time is $\theta(n/ k .k.log k)$ the time complexity is $\theta(n log k)$