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

Question

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()

Answer 1

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.

Answer 2

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!