IN SCALA PROGRAMMING

Write a function unionOfLists that inputs two lists of integers (sorted in ascending order) and returns a list of integers. The function must compute the union of the two input lists to return a list that is also sorted in ascending order. Note that in performing the union, each number can appear at most once in the output list.

Example 1:

Input: List(1, 3, 4, 6) and List(2, 3, 4, 5)

Output: List(1, 2, 3, 4, 5, 6)

Example 2:

Input: List(1, 2, 3, 4) and List(1, 2, 3, 5)

Output: List(1, 2, 3, 4, 5)

Restrictions: Suppose the given lists are of the sizes n and m respectively, the algorithm you use should be of the time complexity O(n + m). Notice that you should never use any sorting program, since any comparison-based sorting algorithm has the time complexity O(k log k) where k is the size of the sorted sequence.

Your program should pass the following tests:

testWithMessage(

unionOfLists(List(1, 3, 5), List(2, 3, 4)),

List(1, 2, 3, 4, 5),

"unionOfLists(List(1, 3, 5), List(2, 3, 4))"

)

testWithMessage(

unionOfLists(List(1), List(1)),

List(1),

"unionOfLists(List(1), List(1))"

)

testWithMessage(

unionOfLists(List(1), List(1,2,3)),

List(1,2,3),

"unionOfLists(List(1), List(1,2,3))"

)

testWithMessage(

unionOfLists(List(1,2,3), List(1)),

List(1,2,3),

"unionOfLists(List(1,2,3), List(1))"

)

testWithMessage(

unionOfLists(List(), List(0)),

List(0),

"unionOfLists(List(), List(0))"

)

testWithMessage(

unionOfLists(List(0), List()),

List(0),

"unionOfLists(List(0), List())"

)

testWithMessage(

unionOfLists(List(2, 4, 6, 8, 10, 12), List(1, 3, 5, 7, 9, 11)),

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12),

"unionOfLists(List(2, 4, 6, 8, 10, 12),List(1, 3, 5, 7, 9, 11))"

)

score=(score*1*15 / 7.0).round / 1.0

passed(score)