Merging Two Sorted Lists in Python In Linear Time

Question

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

Answer 1

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

Answer 2

Here is a working implementation of the merge using only lists which (I think) functions linearly in time.

def mergeLists(a,b, direction):
         c = []
         # assuming ascending sortedness
         if direction == True:
             while a and b:
                 if a[len(a)-1] > b[len(b)-1]:
                     c.append(a.pop())
                 else:
                     c.append(b.pop())
             return (c + a[::-1] + b[::-1])[::-1]
         #assuming descending sortedness
         else:
             while a and b:
                 if a[len(a)-1] < b[len(b)-1]:
                      c.append(a.pop())
                 else:
                      c.append(b.pop())
             return (c+a[::-1]+b[::-1])[::-1]