Merge

Write a program, that merges two sorted fields (in ascending order) holding integer values.

Possible duplicates shall be part of the result set.
An algorithm has to be added to a given code frame.

This is the complete code:

And this is how the algorithm works:

Given three lists.
List one with five elements 1, 2, 4, 6 and 9.
List two with eight elements 1, 3, 5, 6, 7, 8, 9 and 10.
List three, the result list, with thirteen empty slots.

Each list has its own counter, starting at position 1.

We compare the first element in list one with the first element in list two.
In case the element of list one is less then element of list two, it is added to the result list. Otherwise the first element of list two is added.
1 (list one) < 1 (list two)? Nope. We add the value 1 of list two to the result list.

As we already dealt with the first element of list two, we increase the position counter of list two by 1.
As the results list now holds one element, we increase its position counter by 1 as well.
List one remains untouched.

Next we compare the first element of list one with the second element of list two.
1 < 3? Yes. The element of list one is added to the result list.

The result list now holds two elements (1 and 1),  again we increase its counter.
We increase the counter of list one as well.
The position counter of list two remains untouched this time.

We keep repeating this process until either list one or list two runs out of elements.
In our example list one is the first list to run out. 9 is the last value taken from the list.

The last step is to iterate over the remaining list and add its elements to the result list.