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 pyth

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.

StackExchange Code Review Q#98726, answer score: 10