most efficient algorithm to get union of 2 ordered lists

Question

I need to find the union of 2 descending ordered lists (list1 and list2), where the union would be each element from both lists without duplicates. Assume the list elements are integers. I am using big O notation to determine the most efficient algorithm to solve this problem. I know the big O notation for the 1st, but I do not know the big O notation for the 2nd. Can someone tell me the big O notation of the 2nd algorithm so I can decide which algorithm to implement? If someone knows a better algorithm than one of these, could you help me understand that as well? Thanks in advance.

Here are my two algorithms. . .

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Algorithm #1: O(N * log base2 N)

Starting at the first element of list1, 
while(list1 is not at the end of the list) {
    if(the current element in list1 is not in list2)    // Binary Search -> O(log base2 N)
        add the current element in list1 to list2
    go to the next element in list1 }

list2 is now the union of the 2 lists

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Algorithm #2: O(?)

Starting at the first elements of each list,
LOOP_START:
    compare the current elements of the lists
    whichever element is greater, put into a 3rd list called list3
    go to the next element in the list whose element was just inserted into list3
    branch to LOOP_START until either list1 or list2 are at the end of their respective list
insert the remaining elements from either list1 or list2 into list3 (the union)

list3 now contains the union of list1 and list2

Answer 1

Here's my assessment of the situation

• Your first algorithm runs in n log n time: you are doing the binary search for every element in the first list, right?
• Your second algorithm is not entirely complete: you don't say what to do if the elements in the two lists are equal. However, given the right logic for dealing with equal elements, your second algorithm is like the merge part of the merge sort: it will run in linear time (i.e. N). It is optimal, in a sense that you cannot do better than that: you cannot merge two ordered lists without looking at every element in both list at least once.