Question

Pseudocode and algorithm of merging k sorted list with running time O(Nlogk).

Answer 1

Assuming that we have function name Merge(A,B) is available, which combines two sorted lists A and B into single list C and return in time complexity O(|A|+|B|). Here we divide k sorted list into k/2 pairs of list and combine each pair of lists into single list in first step and then repeat the process for k/2 lists available. This process will continue till there is only one list available.

Assume each lists are stored in LIST_QUEUE such that LIST_QUEUE[ i ] will be i^th sorted lists. For simplicity assume k = 2^x for some integer x.

ALGORITHM(LIST_QUEUE , k)

1. While k > 1:-

2........For i = 1 to k :-

3.................A = LIST_QUEUE.Dequeue //dequeue the list form list queue

4.................B = LIST_QUEUE.Dequeue //dequeue the list form list queue

5.................C = Merge(A,B)

6.................LIST_QUEUE.Enqueue(C) //Enqueue sorted list C

7. If k == 1 then

8........return LIST_QUEUE.Dequeue //return the final single sorted list

Here since at each iterations, merging process over entire N elements is going on, which takes O(N) times. And this process will repeat (log k) times, hence total time complexity will be O(N log k).