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.
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
• Am I correct to think that pop() is O(1) and pop(1) is O(n)? Feb 7, 2017 at 21:13
• Also, are we not assuming that the two list parameters have the same direction of sort (ascending or descending)? In your counter example you pick different directions. Feb 7, 2017 at 21:15
• @MadPhysicist exactly, popping from the left side of a list would require the list to be reallocated. Feb 7, 2017 at 21:15
• @MadPhysicist ah, my bad - that was a typo - the lists are [1, 2, 3] and [4, 5, 6], same direction, sorry. Feb 7, 2017 at 21:16
• I implemented the code using only lists. Could you take a look? Feb 7, 2017 at 22:19

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]