# Google's Python exercise about lists very different from the given solution

I found some Python exercises that were made by Google in their Python classes and decided to spend some time with them.

Given the following description:

E. Given two lists sorted in increasing order, create and return a merged ist of all the elements in sorted order. You may modify the passed in lists. deally, the solution should work in "linear" time, making a single pass of both lists.

So, knowing that comparing two characters is $$\O(1)\$$, Python's sorted() function in this situation is $$\O(n \log{n})\$$ and thinking that merging two lists into a new one is $$\O(k)\$$ where $$\k\$$ the number of elements in list1 + list2, which is quite "linear" in the sense of what was asked, I did...

def linear_merge(list1, list2):
return sorted(list1 + list2)


However, when looking at the problem's solution, I found it to be somewhat different:

def linear_merge(list1, list2):
result = []
# Look at the two lists so long as both are non-empty.
# Take whichever element [0] is smaller.
while len(list1) and len(list2):
if list1[0] < list2[0]:
result.append(list1.pop(0))
else:
result.append(list2.pop(0))

# Now tack on what's left
result.extend(list1)
result.extend(list2)
return result


which is followed by the following comment:

Note: the solution above is kind of cute, but unforunately list.pop(0) is not constant time with the standard Python list implementation, so the above is not strictly linear time. An alternate approach uses pop(-1) to remove the endmost elements from each list, building a solution list which is backwards. Then use reversed() to put the result back in the correct order. That solution works in linear time, but is more ugly.

This confused me a little bit, since my solution looks... better in general (code and complexity, given the last comment paragraph).

Are any of my assumptions about my version of the code wrong?

Keep in mind that I wrote this version using Python3, when instead google's python classes uses Python2. I'm not really sure, but this may have something to do with it.

Here is the rest of the related source to give a full example:

def test(got, expected):
if got == expected:
prefix = ' OK '
else:
prefix = '  X '
print('{} got: {} expected: {}'.format(prefix, repr(got), repr(expected)))

# Calls the above functions with interesting inputs.
def main():
print('linear_merge')
test(linear_merge(['aa', 'xx', 'zz'], ['bb', 'cc']),
['aa', 'bb', 'cc', 'xx', 'zz'])
test(linear_merge(['aa', 'xx'], ['bb', 'cc', 'zz']),
['aa', 'bb', 'cc', 'xx', 'zz'])
test(linear_merge(['aa', 'aa'], ['aa', 'bb', 'bb']),
['aa', 'aa', 'aa', 'bb', 'bb'])

if __name__ == '__main__':
main()

• It depends what you consider to be the goal of the exercise. If this is a stepping-stone towards implementing mergesort, then using the built-in sorted() function is cheating. Furthermore, it could be considered overkill, since it fails to take advantage of the knowledge that the inputs are each already sorted. On the other hand, if you were developing a larger application and this were one programming task among the dozens of features you had to implement in a day, I would absolutely consider take your shortcut. – 200_success Aug 8 '15 at 4:26

In a nutshell, yours is better, for two reasons.

First, Python isn't designed for speed. It's decently fast, but the goal is code like yours: so clear, concise, obvious, and readable that anyone can glance at it and immediately see what it does. You can then spend the rest of the project's development time working on the difficult problems (like attending meetings).

Second, the "answer" code doesn't really answer the exercise, as it notes. It looks right in theory, but popping elements from the beginning of a list is not the most performant operation in most languages, including Python. It would be a more reasonable solution with a linked list, which is a type that was probably omitted from Python precisely because its utility is mostly limited to fixing the micro-optimizations in bloated code. This is like optimizing a recursive function by making it tail-recursive, and then admitting that it doesn't make any difference because Python doesn't have tail call optimization.

If you were using this code in a real program and determined through actual testing that this linear_merge function was taking too much time due to the extra sorting, you might then be justified in optimizing it.

For fun, here's something with indexing instead of pop():

def linear_merge(list1, list2):
result = []
c1 = c2 = 0
while c1<len(list1) and c2<len(list2):
if list1[c1] <= list2[c2]:
result.append(list1[c1])
c1 += 1
else:
result.append(list2[c2])
c2 += 1
result.extend(list2[c1:])
result.extend(list1[c2:])
return result


This might be faster due to not pop()ing items from the beginning of each list, but it also might be slower (or possibly more memory-intensive) due to having to slice a list at the end. I leave it as an exercise to you to time these approaches... but remember that the most important time to conserve is usually your own, not your computer's.

• You typically make the check inside the while loop if list1[c1] <= list2[c2]:, so that items from list1 get merged before items in list2 in case of equality. It is part of what makes mergesort a stable sort, so it is pretty relevant to be aware of it. Also, I like it better skipping the last if / else clause, and unconditionally extending result with both list1[c1:] and list2[c2:], since extending with an empty list leaves the original list unchanged. – Jaime Aug 1 '15 at 17:28
• @Jaime - Good points; I'll edit. – TigerhawkT3 Aug 1 '15 at 19:06

Actually, although not immediately obvious, your solution is $O(n)$... The sorting algorithm used by Python is Timsort, thus named after its inventor, Tim Peters, author also of The Zen of Python.

It has many subtleties and refinements, but at a very high level, Timsort works by scanning the array to find sorted runs, i.e. contiguous subarrays already in sorted order, then merging them into larger sorted subarrays. When run on an array made out of two concatenated sorted subarrays, it will identify both of them as runs, then merge them into a single sorted array, all in linear time.

That's one of the beauties of Timsort: that it can beat the famous $O(n \log n)$ bound if the array is highly structured. Your particular case happens to be one of the ones that run in linear time!