Merging k sorted lists

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.

	/**
	* Created with IntelliJ IDEA.
	* User: Ravi
	* Date: 11/1/13
	* Time: 1:18 PM
	* To change this template use File \| Settings \| File Templates.
	*/
	import java.util.ArrayList;
	import java.util.PriorityQueue;

	public class MergeSortedLists {
	public static void main(String[] args)
	{
	ArrayList< ArrayList<Integer> > sortedLists = new ArrayList< ArrayList<Integer> > ();

	//create 5 sorted lists as input
	for( int i = 0; i < 5; i++ )
	{
	ArrayList<Integer> list = new ArrayList<Integer>();

	for( int j = 0; j < 5; j++ )
	{
	list.add( i + (5*j) );
	}
	sortedLists.add(list);
	}


	//Print the sorted lists before merging
	System.out.println("Sorted lists before merging:");
	for( ArrayList<Integer> l: sortedLists )
	{
	for( int num:l)
	{
	System.out.print( num + " ");
	}
	System.out.println();
	}

	//merge the sorted lists
	ArrayList<Integer> resultList = mergeSortedLists(sortedLists);

	//print the result list
	System.out.println("Merged list");
	for(int num:resultList)
	{
	System.out.print(num + " ");
	}
	}
	public static ArrayList<Integer> mergeSortedLists( ArrayList< ArrayList<Integer> > lists)
	{
	PriorityQueue<PQEntry> pq = new PriorityQueue<PQEntry>();
	// Starting indices of not-yet-processed elements of each list
	int[] sIndex = new int[ lists.size() ];
	int i = 0;

	//Initially add the first element of each list into priority queue
	//update the sIndex[] entries to 1 for all lists
	for( i = 0; i < lists.size(); i++ )
	{
	ArrayList<Integer> list = lists.get(i);

	pq.add( new PQEntry(list.get(0),i) );
	sIndex[i] = 1;
	}

	ArrayList<Integer> resultList = new ArrayList<Integer>();

	while ( !pq.isEmpty() )
	{
	PQEntry entry = pq.poll();// Remove minimum entry from the priority queue
	resultList.add(entry.data);

	int minListInd = entry.listInd;//min-list from which the element is just removed

	int nextInd = sIndex[minListInd]; //index of the next element in min-list

	//If the min-list has un-processed elements, add it to priority queue and update the index
	if( nextInd < lists.get(minListInd).size() )
	{
	pq.add( new PQEntry(lists.get(minListInd).get(nextInd), minListInd) );
	sIndex[minListInd]++;
	}
	}
	return resultList;
	}

	static class PQEntry implements Comparable<PQEntry>
	{
	public int data;
	public int listInd;

	public PQEntry(int d, int li)
	{
	data = d;
	listInd = li;
	}
	@Override
	public int compareTo(PQEntry other)
	{
	return data - other.data;
	}
	}
	}

view raw MergeSortedLists.java hosted with

by GitHub

Leave a Reply Cancel reply