What is the difference between these two python codes?

Question

I recently began to learn a Python

I downloaded a basic exercise file from https://developers.google.com/edu/python/exercises/basic

and I wrote the code for following exercise.

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.

My code was

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

However, solution provided is

def linear_merge(list1, list2):
  result = []
  while len(list1) and len(list2):
    if list1[0] < list2[0]:
      result.append(list1.pop(0))
    else:
      result.append(list2.pop(0))


  result.extend(list1)
  result.extend(list2)
  return result

I ran sample example with my code and It worked.

However, I don't know why the solution is quite longer than mine.

Is there an actual difference between two codes? Do I misunderstood the problem?

p.s. Also, what is the meaning of the last sentence in the question which is saying 'linear' time?

Maybe part of the point of the exercise was that you don't use any ready-made sorting algorithms. But your algorithm is less efficient. You discard the fact that the input lists are already sorted. — juanchopanza, Jan 25 '16 at 08:27
There are several duplicated questions: http://stackoverflow.com/questions/5840764/question-on-a-solution-from-google-python-class-day, http://stackoverflow.com/questions/2488889/how-can-i-merge-two-lists-and-sort-them-working-in-linear-time, http://stackoverflow.com/questions/4173225/my-implementation-of-merging-two-sorted-lists-in-linear-time-what-could-be-imp, http://stackoverflow.com/questions/7237875/linear-merging-for-lists-in-python — West, Jan 25 '16 at 08:50

bereal · Answer 1 · 2016-01-25T11:08:21.360

The "longer" solution has better asymptotic complexity: sorted() is O(n*log n), and manual merging, given that the lists are ordered, is O(n), where n = len(list1) + len(list2).

As the length of the lists grows, the second algorithm will perform much better: if the total length grows twice, it will take just twice longer. That's roughly what's meant by "linear time". That said, consider spending few hours reading about the complexity in general, that's perhaps the best investment of time for a novice programmer.

UPDATE: Actually, the devil is in the details. Since list.pop(0) is O(n), the latter implementation is even worse. Just going through the lists without modifying them would make much more sense.

What is the difference between these two python codes?

1 Answers1