Merge sorted lists

Question

I want to write a function that merges two sorted lists in Python 3.

For example:

>> merge_lists([2, 5, 9], [1, 6, 8, 10])
[1, 2, 5, 6, 8, 9, 10]

My implementation is as follows:

def merge_lists(L1, L2):
 Outlist = []
 while (L1 and L2):
 if (L1[0] <= L2[0]):
 item = L1.pop(0)
 Outlist.append(item)
 else:
 item = L2.pop(0)
 Outlist.append(item)
 Outlist.extend(L1 if L1 else L2)
 return Outlist

Can I make it better or more readable?

Answer 1

1. Python's style guide says to use lower_snake_case for variable names.
2. You can use a turnery to assign the desired list to a variable to remove the duplicate code.
3. L1.pop(0) runs in \$O(n)\$ time, making your code \$O(n^2)\$. You can fix this by using collections.deque.

import collections
def merge_lists(list_1, list_2):
 list_1 = collections.deque(list_1)
 list_2 = collections.deque(list_2)
 outlist = []
 while (list_1 and list_2):
 list_ = list_1 if list_1[0] <= list_2[0] else list_2
 item = list_.popleft()
 outlist.append(item)
 outlist.extend(list_1 if list_1 else list_2)
 return outlist

---

As highlighted in one of my previous questions, you can replace this with heapq.merge.

• Roland Illig: Did you mean ternary instead of turnery?
• Roland Illig: The whole point of hand-writing this algorithm was to be fast. Otherwise a simple out = []; out.extend(a); out.extend(b); sort(out); return out would have been enough. Converting the lists into deques copies all elements, doesn't it?
• Oscar Smith: The funny thing is that that method will actually be almost as fast as a proper merge. Since python uses TimSort, it will take full advantage of the order already in the data. My guess is that sorting will be the 2nd fastest solution (2nd only to heapq.merge`
• Peilonrayz: @RolandIllig reread point 2. Each loop you're copying each and every value in the loop anyway. You didn't tag this performance, but sorted and heapq are likely to be tons faster than anything you write.

Answer 2

Since lists are passed by reference, the two lists that are passed as arguments will be half-empty after the function returns.

a = [1, 2, 4]
b = [3, 5]
merge_lists(a, b)
print(a) # is empty now but shouldn't
print(b) # only contains 5 now

Therefore you should not use list.pop at all but instead iterate over the lists via indexes, since these don't modify the lists.

Instead of the if-then-else expression at the end, you can just write:

Outlist.extend(L1)
Outlist.extend(L2)