Given K sorted lists, how to merge them into a single sorted list?
Let total number of elements in K sorted lists is N. We have to form a single sorted list of length N.
For example let us consider the following input lists
{4, 19, 27}
{1, 6, 50, 73}
{9, 45, 59, 67}
The output should be {1, 4, 6, 9, 19, 27, 45, 50, 59, 67, 73}.
In this post, we discuss an efficient approach by using priority queues (heaps). This problem is one of the nice examples of using priority queues.
Here is how the algorithm works.
- Add the first elements from all the lists into a priority queue along with their list indices.
- Until the priority queue is empty, do the following
- Remove the minimum element from the priority queue and add it to the result list. Let this minimum element belongs to min_list.
- Add the next element from min_list to the priority queue if there exists at least one element.
Here is the Java implementation of the above algorithm.
Time complexity of this algorithm is O(N log K) as we have N elements in total, and insert and remove-min operation of the priority queue takes O(log k) time.