Merging Two Sorted Lists in Python In Linear Time

I am trying to implement a merge of two sorted lists of integers in Python using only the basic list abstract data type operations. That is, I do not want to use sorted() which comes with Python.

Could someone tell me if this code is alright? Also, am I correct to understand that it is linear to the core? That is, it uses no Python operation that is non-linear in time?

def mergeSortedLists(list1, list2):
     list3 = []
     while list1 and list2:
         if list1[len(list1) - 1] > list2[len(list2) - 1]:
             list3.append(list1.pop())
         else:
             list3.append(list2.pop())
     return list3 + list1 + list2

Correctness

First of all, your merging code is not correct. If you have list1 = [1, 2, 3] and list2 = [4, 5, 6], the result would be [6, 5, 4, 1, 2, 3].

Assuming, you are up to [1, 2, 3, 4, 5, 6], you should be comparing the first elements of the lists. The problem with that is that "pop" from the left is an expensive operation for a regular Python list. Switching to the collections.deque double-ended queue would solve it - popleft() is O(1).

Fixed version:

from collections import deque

def merge_sorted_lists(left, right):
    """
    Merge sort merging function.
    TODO: Improve, add examples."""
    result = deque()

    left = deque(left)
    right = deque(right)

    while left and right:
        if left[0] > right[0]:
            result.append(right.popleft())
        else:
            result.append(left.popleft())
    return result + left + right

Time Complexity Analysis (for your "incorrect" version)

You are operating Python lists, according to the Time Complexity page:

• the "get length" operation is O(1) (even though you can use -1 in place of len(list1) - 1 and len(list2) - 1)

• the "pop from the right" operation is O(1)

• the "append to the right" operation is O(1)

Which leads to overall complexity as O(N + M) where N is the length of the list1 and M - the length of the list list2.

Stylistic issues:

• as per PEP8 guide, use 4 spaces for indentation

• the function name should be merge_sorted_lists according to PEP8 variable naming guidelines

• list1 should be better called left, list2 - right, list3 - result for clarity purposes

• missing docstring explaining what function does

StackExchange Code Review Q#154743, answer score: 7