October 23, 2016 by LanceShi

# 6.4 Merge two sorted list

## The problem

Suppose we have two sorted Integer list, now we want to merge them together into one list. And it should still be sorted. For example, if we have these two lists:

3, 6, 9 , 12, 18

And

5, 8, 10, 11, 20

The result should be

3, 5, 6, 8, 9, 10, 11, 12, 18, 20

## The code

This problem can be a bit difficult for you. Actually, a lot of companies are using this question as their interview question for software engineers. Don’t feel discouraged if you find it hard for you. Just read the code and make sure you understand it.

public class Util { public static List<Integer> mergeSortedLists(List<Integer> aList, List<Integer> bList) { List<Integer> mergedList = new List<Integer>(); Integer aIndex = 0; Integer bIndex = 0; while (aIndex < aList.size() && bIndex < bList.size()) { if(aList[aIndex] < bList[bIndex]) { mergedList.add(aList[aIndex]); aIndex++; } else { mergedList.add(bList[bIndex]); bIndex++; } } //After this loop, the array with smaller greatest number will be all merged. But the other one is not. //So we need to continue merge the rest of it. if(aIndex < aList.size()) { for(Integer i = aIndex; i < aList.size(); i++) { mergedList.add(aList[i]); } } else if(bIndex < bList.size()) { for(Integer i = bIndex; i < bList.size(); i++) { mergedList.add(bList[i]); } } return mergedList; } //... }

And the test code:

List<Integer> firstList = new List<Integer>{3, 6, 9, 12, 18}; List<Integer> secondList = new List<Integer>{5, 8, 10, 11, 20}; List<Integer> mergedList = Util.mergeSortedLists(firstList, secondList); System.debug(mergedList);

## A bit explanation

The resolution of this question illustrates how we analyse and resolve an issue in program.

When we look at two sorted list, we just compare them one by one. If the number in aList is higher, we copy the number in bList into mergedList, and make the current bList number to be next one. Let’s look at our example:

At first, both aIndex and bIndex are 0. So we compare the first elements of both lists: 3 and 5. Since 3 is smaller. So we copy 3 into mergedList. And add one for aIndex.

Now aIndex is 1 and bIndex is still 0. So we can compare between 6 and 5. 5 is smaller and we copy 5 into mergedList and add one for bIndex.

This will continue until one of the lists run out of numbers, which should be the one who has relatively smaller largest number. In this case, should be aList. Because 18 is smaller than 20.

However, it only means one list is running out of number, the other list is still not yet.

So we need to copy the rest of the other list’s number into merged list. That’s why we had another loop.

## Exercise

Till now we have finished all our training examples based on previous knowledge. I hope you can fully understand all the examples in this chapter. After that, you should be able to write the code for them all by yourself without further looking at my code.

At this point, I would encourage you to try writing code for the first 10 archive question in Euler project. If you find them difficult, it is okay. You can google other people’s resolution to them. I will also write the apex version in my github later on.

## Leave a Reply