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.