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.

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)