Press "Enter" to skip to content

Merge Multiple Sorted Lists of Strings in Java

Ajk 0

How would you Merge Multiple Sorted Lists of Strings into one list? I got asked this very question in an interview myself. And to my surprise I was not very sharp on it. The question is about developing an algorithm to find how to merge an arbitrary number K of Sorted Lists of Strings into 1.

So let us start with our usual clarification portion and make some assumptions:

  1. Obviously all the lists are sorted. (As advised by the question itself)
  2. The lists contain Strings. (Again, denoted by the question)
  3. Let us denote the longest list as having N elements. (This will help us develop big-O notations later)

There is not any other clarifications that we need. Hence we can start to think about a way to solve this.
How would our own brain solve this? It would just compare each first item on the list, write it down and remove it from the list, until all element of all lists are out. Seems like we have our hands on a brute force solution!

Merge Multiple Sorted Lists of Strings – Recursive Algorithm

  1. While lists are not empty:
  2. For each List:
  3. Compare the heads of the lists
  4. Remove and print out the smallest number

But let us do a little bit space-time complexity analysis on this. We are looping through each list (K) for each element across lists (N*K). The result would be that our Time Complexity is O(nk2). A note to make is that by having the lists as LinkedLists or by keeping an index in the lists instead of actually removing the item, we could make our last step (Remove and print out the head of the list), O(1).

The auxiliary space complexity on the other hand is O(1) since we are not keeping any data structured in our algorithm ;D. Given this info let us think about any trade-offs we can make by using some space and lowering our runtime.

For this we can try to take another look at the problem and see if we can split it into sub-problems. As it turns out this question is a little bit similar to MergeSort. Quoting from our MergeSort post:

Merge Sort Algorithm

  1. Divide the unsorted list into 2 sublists.
  2. Sort them (using recursion of merge sort).
  3. Merge the two sorted list in a merge step to produce 1 sorted list.

For more information you can take a look at this excellent explanation from Khan Academy

Now in our current problem’s case to merge multiple sorted lists of strings, we already have the lists sorted. So all we need to do is focus on the algorithm to merge them. Our current algorithm will look like this:

Merge Multiple Sorted Lists of Strings – Loop Algorithm

  1. While there are more than 1 lists left.
  2. Merge a pair of lists into 1 and append it to the list of lists. Remove the merged ones.

Note that the above can also translate the above solution into a recursive solution:

Merge Multiple Sorted Lists of Strings – Recursive Algorithm

  1. Divide the lists into two groups.
  2. Merge each group on its own (in a recursive fashion).
  3. Merge the two groups together.

So let’s try to put both those algorithms (which are fairly similar) into a code implementation. Note that they should be fairly similar, as the merge step will look the same.

Merge Multiple Sorted Lists of Strings – Java Loop Implementation

So for some quick analysis. We are merging lists in a tree fashion. At the beginning step we are merging N/2 lists, whereas at the end step we are merging 2. Therefore we are doing O(K*log(K)) merges. For each merge we are going through the elements of both lists. Denoting their length with N, our time complexity for doing 1 merge will be (O(N)). Hence our final time complexity will be found by multiplying those two actions, which will mean O(N*K*log(K)). A lot better than our brute force approach isn’t it! On the other hand, since we are keeping all lists with all elements in an auxiliary data structure, our space complexity will be O(N*K).

So far so good! But why don’t we take a stab at the recursive approach? If you are still beginning in Computer Science, brush up your knowledge by reading this small lecture on recursion

Merge Multiple Sorted Lists of Strings – Java Recursive Implementation

Homework #1: What’s the time and space complexity of the above code? Can you explain why?

Seems like this was not too hard either. As you can see if you start on step by step blocks and try to reason out the problem first before jumping into coding, the whole process becomes much easier.

Now what if our interviewer does not like this or for some reason wants to point us to a different direction? Another solution, which in my opinion is a little less straight forward than the ones above, is to use a Heap data structure.

Quoting from wikipedia:

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a “max heap” or a “min heap”.

You can see a max-heap representation below:
Merge multiple sorted list of strings in Java - Max-Heap

The main advantage of using a heap, is that we can keep our lists in a “semi-ordered” way. The idea behind the semi-ordered is that we can quickly reorder the heap (a method that is commonly called Heapify). How would our problem benefit from this data structure? Well, if we can keep all the lists in a semi-ordered manner in a min-heap, the we could take the minimum element in O(1) and re structure the tree in O(log(K)). This is a drastic win from our brute force approach which had to always go through all the lists and was going to take O(K) to get a single element! The rest of the algorithm to merge multiple sorted lists of strings should be approximately the same. So let us put our thoughts into more concise steps.

Merge Multiple Sorted Lists of Strings – Heap Algorithm

  1. Put all the leasts in a min-heap.
  2. While the heap has still more elements.
  3. Pop the first minimum / top element and put it into a return list.

Sounds pretty straight forward? The data structure in Java that represents a Heap is a Priority Queue. So with that in mind let us go ahead and write some code.

Merge Multiple Sorted Lists of Strings – Java Heap Implementation

I will leave you as a homework to think through the space and complexity of this one too :). Although we did get an idea on the algorithm build up.

I think this is pretty much all there is to this question. The heap solution is slightly trickier to get to, but you might be able to earn some brownie points in an interview if you mention and implement it. The first two solutions should be doable by anyone that has encountered Merge Sort before.

Hope you guys enjoyed it… and I’ll see you guys next time! ;D

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *