How to merge two big Lists in one sorted List in Java?

Question

I had an interview today, and they gave me:

List A has:

f 
google 
gfk 
fat 
...

List B has:

hgt 
google 
koko 
fat 
ffta 
...

They asked me to merge these two list in one sorted List C.

What I said:

I added List B to List A, then I created a Set from List A, then create a List from the Set. The interviewer told me the lists are big, and this method will not be good for performance, he said it will be a nlog(n).

What would be a better approach to this problem?

• arshajii: I'm assuming these are lists of strings, and you want to sort listC based on the strings' compareTo methods?
• Tony K.: Any info about the original lists? Are they array based?
• Garrett Hall: AFAIK If both lists are unsorted then you cannot do better than nlog(n), maybe you misunderstood the question?
• tdelaney18: What data structure is being used?
• akram: Yes they are list of Strings. they just draw List in the white board, I asked if the original Lists were sorted, he said yes.

Answer 1

Well your method would require O(3N) additional space (the concatenated List, the Set and the result List), which is its main inefficiency.

I would sort ListA and ListB with whatever sorting algorithm you choose (QuickSort is in-place requiring O(1) space; I believe Java's default sort strategy is MergeSort which typically requires O(N) additional space), then use a MergeSort-like algorithm to examine the "current" index of ListA to the current index of ListB, insert the element that should come first into ListC, and increment that list's "current" index count. Still NlogN but you avoid multiple rounds of converting from collection to collection; this strategy only uses O(N) additional space (for ListC; along the way you'll need N/2 space if you MergeSort the source lists).

IMO the lower bound for an algorithm to do what the interviewer wanted would be O(NlogN). While the best solution would have less additional space and be more efficient within that growth model, you simply can't sort two unsorted lists of strings in less than NlogN time.

EDIT: Java's not my forte (I'm a SeeSharper by trade), but the code would probably look something like:

Collections.sort(listA);
Collections.sort(listB);
ListIterator<String> aIter = listA.listIterator();
ListIterator<String> bIter = listB.listIterator();
List<String> listC = new List<String>();
while(aIter.hasNext() || bIter.hasNext())
{
 if(!bIter.hasNext())
 listC.add(aIter.next());
 else if(!aIter.hasNext())
 listC.add(bIter.next());
 else
 {
 //kinda smells from a C# background to mix the List and its Iterator, 
 //but this avoids "backtracking" the Iterators when their value isn't selected.
 String a = listA[aIter.nextIndex()];
 String b = listB[bIter.nextIndex()];
 if(a==b) 
 {
 listC.add(aIter.next());
 listC.add(bIter.next());
 }
 else if(a.CompareTo(b) < 0)
 listC.add(aIter.next());
 else
 listC.add(bIter.next()); 
 }
}

• Fred Foo: Recent versions of Java use Timsort, but merge sort on linked lists can be done nearly in-place with O(lg n) extra memory, just like quicksort.
• akram: Thank you KeithS for the explaination, can you please give me a code exapmle on how to acheive this ?
• akram: I did not understand this : then use a MergeSort-like algorithm to examine the "current" index of ListA to the current index of ListB
• KeithS: Basically, the statement you found confusing is how MergeSort merges two sublists (which have been sorted by recursive subiterations of the algorithm). The basic idea is, take a look at the first index of each collection (which is the initial "current" index). Whichever element should come first, take it and put it in the result list, then increment the current index for that list. Continue comparing the elements at the current index of each list until all elements of both lists have been put into the result list.
• akram: I appreciate your help KeithS