Question on a solution from Google python class day

Hey, I'm trying to learn a bit about Python so I decided to follow Google's tutorial. Anyway I had a question regarding one of their solution for an exercise.

Where I did it开发者_运维百科 like this way.

# E. Given two lists sorted in increasing order, create and return a merged
# list of all the elements in sorted order. You may modify the passed in lists.
# Ideally, the solution should work in "linear" time, making a single
# pass of both lists.
def linear_merge(list1, list2):
  # +++your code here+++
  return sorted(list1 + list2)

However they did it in a more complicated way. So is Google's solution quicker? Because I noticed in the comment lines that the solution should work in "linear" time, which mine probably isn't?

This is their solution

def linear_merge(list1, list2):
  # +++your code here+++
  # LAB(begin solution)
  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

this could be another soln? #

    def linear_merge(list1, list2):
            tmp = []
            while len(list1) and len(list2):
                    #print list1[-1],list2[-1]
                    if list1[-1] > list2[-1]:
                            tmp.append(list1.pop())
                    else:
                            tmp.append(list2.pop())
                    #print "tmp = ",tmp

            #print list1,list2
            tmp = tmp + list1
            tmp = tmp + list2
            tmp.reverse()
            return tmp

Yours is not linear, but that doesn't mean it's slower. Algorithmic complexity ("big-oh notation") is often only a rough guide and always only tells one part of the story.

However, theirs isn't linear either, though it may appear to be at first blush. Popping from a list requires moving all later items, so popping from the front requires moving all remaining elements.

It is a good exercise to think about how to make this O(n). The below is in the same spirit as the given solution, but avoids its pitfalls while generalizing to more than 2 lists for the sake of exercise. For exactly 2 lists, you could remove the heap handling and simply test which next item is smaller.

import heapq

def iter_linear_merge(*args):
  """Yield non-decreasing items from sorted a and b."""
  # Technically, [1, 1, 2, 2] isn't an "increasing" sequence,
  # but it is non-decreasing.

  nexts = []
  for x in args:
    x = iter(x)
    for n in x:
      heapq.heappush(nexts, (n, x))
      break

  while len(nexts) >= 2:
    n, x = heapq.heappop(nexts)
    yield n
    for n in x:
      heapq.heappush(nexts, (n, x))
      break

  if nexts:  # Degenerate case of the heap, not strictly required.
    n, x = nexts[0]
    yield n
    for n in x:
      yield n

Instead of the last if-for, the while loop condition could be changed to just "nexts", but it is probably worthwhile to specially handle the last remaining iterator.

If you want to strictly return a list instead of an iterator:

def linear_merge(*args):
  return list(iter_linear_merge(*args))

With mostly-sorted data, timsort approaches linear. Also, your code doesn't have to screw around with the lists themselves. Therefore, your code is possibly just a bit faster.

But that's what timing is for, innit?

I think the issue here is that the tutorial is illustrating how to implement a well-known algorithm called 'merge' in Python. The tutorial is not expecting you to actually use a library sorting function in the solution.

sorted() is probably O(nlgn); then your solution cannot be linear in the worst case.

It is important to understand how merge() works because it is useful in many other algorithms. It exploits the fact the input lists are individually sorted, moving through each list sequentially and selecting the smallest option. The remaining items are appended at the end.

The question isn't which is 'quicker' for a given input case but about which algorithm is more complex.

There are hybrid variations of merge-sort which fall back on another sorting algorithm once the input list size drops below a certain threshold.