How to efficiently left outer join two sorted lists

Question

I have two lists which are already sorted. I need to left outer join them. The following code gets the job done:

left_sorted_list = [1, 2, 3, 4, 5]
right_sorted_list = [[2, 21], [4, 45], [6, 67]]
right_dict = {r[0]: r[1] for r in right_sorted_list}
left_outer_join = [[l, right_dict[l] if l in right_dict.keys() else None]
                   for l in left_sorted_list]
print(left_outer_join)
[[1, None], [2, 21], [3, None], [4, 45], [5, None]]

However, I am not sure if this approach is very efficient. Is there a more efficient way to utilize the fact that the right list is already sorted, without writing loops?

Edit: the keys I am joining on are unique both in left and right lists.

Answer 1

This answer depends directly on two comments that mgilson made to the OP's question.

This is no more efficient than what you have, but it is more pythonic.

left_sorted_list = [1, 2, 3, 4, 5]
right_sorted_list = [[2, 21], [4, 45]]

right_dict = dict(right_sorted_list)
left_outer_join = [[l, right_dict.get(l)] for l in left_sorted_list] 

As far as time complexity goes, left_sorted_list and right_sorted_list are each iterated over once so they are both O(N). For the dictionary look-ups the average look-up is O(1), so looking up all keys is also O(N). Your time complexity isn't going to get much better than what you already have.