Merging Two Sorted Lists in Python In Linear Time
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] &gt; 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