How can I merge two lists and sort them working in 'linear' time?

Question

I have this, and it works:

# 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):
  finalList = []
  for item in list1:
    finalList.append(item)
  for item in list2:
    finalList.append(item)
  finalList.sort()
  return finalList
  # +++your code here+++
  return

But, I'd really like to learn this stuff well. :) What does 'linear' time mean?

Solution 1

Linear means O(n) in Big O notation, while your code uses a sort() which is most likely O(nlogn).

The question is asking for the standard merge algorithm. A simple Python implementation would be:

def merge(l, m):
    result = []
    i = j = 0
    total = len(l) + len(m)
    while len(result) != total:
        if len(l) == i:
            result += m[j:]
            break
        elif len(m) == j:
            result += l[i:]
            break
        elif l[i] < m[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(m[j])
            j += 1
    return result

>>> merge([1,2,6,7], [1,3,5,9])
[1, 1, 2, 3, 5, 6, 7, 9]

Solution 2

Linear time means that the runtime of the program is proportional to the length of the input. In this case the input consists of two lists. If the lists are twice as long, then the program will run approximately twice as long. Technically, we say that the algorithm should be O(n), where n is the size of the input (in this case the length of the two input lists combined).

This appears to be homework, so I will no supply you with an answer. Even though this is not homework, I am of the opinion that you will be best served by taking a pen and a piece of paper, construct two smallish example lists which are sorted, and figure out how you would merge those two lists, by hand. Once you figured that out, implementing the algorithm is a piece of cake.

(If all goes well, you will notice that you need to iterate over each list only once, in a single direction. That means that the algorithm is indeed linear. Good luck!)

Solution 3

If you build the result in reverse sorted order, you can use pop() and still be O(N)
pop() from the right end of the list does not require shifting the elements, so is O(1)
Reversing the list before we return it is O(N)

>>> def merge(l, r):
...     result = []
...     while l and r:
...         if l[-1] > r[-1]:
...             result.append(l.pop())
...         else:
...             result.append(r.pop())
...     result+=(l+r)[::-1]
...     result.reverse()
...     return result
... 
>>> merge([1,2,6,7], [1,3,5,9])
[1, 1, 2, 3, 5, 6, 7, 9]

Solution 4

This thread contains various implementations of a linear-time merge algorithm. Note that for practical purposes, you would use heapq.merge.

View more solutions

Comments

[Li0liQ]

@Sergio Tapia But it's a nice answer anyway.

[Admin]

Useful for theory, but it doesn't explain whatsoever in code how to implement something keeping that in mind.

[Stephan202]

@Sergio: I'm sorry, that wasn't clear yet when I answered. Regardless, I think that this is the kind of exercise that is best figured out on one's own. Doing that is much more rewarding and beneficial in the long run.

[Mike Graham]

Note that since you use .pop(0), your algorithm is actually quadratic (if l and m are lists). A linear replacement would keep track of indeces or use iter(l) and iter(m) and use next instead of pop(0).

[Max Shawabkeh]

@Mike: You are right. Fix edited in. Having a convenient API for common data structures can really desensitize one to obvious lower-level issues.

[helpermethod]

+1 Really cool solution. Never seen the merge implemented like this in any book :-).

[Sigur]

Very very interesting method. Elegant in my opinion.