My implementation of merging two sorted lists in linear time - what could be improved?

Question

Fromg Google's Python Class:

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.

Here's my solution:

def linear_merge(list1, list2):
  merged_list = []
  i = 0
  j = 0

  while True:
    if i == len(list1):
        return merged_list + list2[j:]
    if j == len(list2):
        return merged_list + list1[i:]

    if list1[i] <= list2[j]:
        merged_list.append(list1[i])
        i += 1
    else:
        merged_list.append(list2[j])
        j += 1

First of all, is it okay to use an infinite loop here? Should I break out of the loop using the break keyword when I'm done merging the list, or are the returns okay here?

I've seen similar questions asked here, and all the solutions look quite similar to mine, i.e. very C-like. Is there no more python-like solution? Or is this because of the nature of the algorithm?

Answer 1

This question covers this in more detail than you probably need. ;) The chosen answer matches your requirement. If I needed to do this myself, I would do it in the way that dbr described in his or her answer (add the lists together, sort the new list) as it is very simple.

EDIT:

I'm adding an implementation below. I actually saw this in another answer here which seems to have been deleted. I'm just hoping it wasn't deleted because it had an error which I'm not catching. ;)

def mergeSortedLists(a, b):
    l = []
    while a and b:
        if a[0] < b[0]:
            l.append(a.pop(0))
        else:
            l.append(b.pop(0))
    return l + a + b

Answer 2

Here's a generator approach. You've probably noticed that a whole lot of these "generate lists" can be done well as generator functions. They're very useful: they don't require you to generate the whole list before using data from it, to keep the whole list in memory, and you can use them to directly generate many data types, not just lists.

This works if passed any iterator, not just lists.

This approach also passes one of the more useful tests: it behaves well when passed an infinite or near-infinite iterator, eg. linear_merge(xrange(10**9), xrange(10**9)).

The redundancy in the two cases could probably be reduced, which would be useful if you wanted to support merging more than two lists, but for clarity I didn't do that here.

def linear_merge(list1, list2):
    """
    >>> a = [1, 3, 5, 7]
    >>> b = [2, 4, 6, 8]
    >>> [i for i in linear_merge(a, b)]
    [1, 2, 3, 4, 5, 6, 7, 8]
    >>> [i for i in linear_merge(b, a)]
    [1, 2, 3, 4, 5, 6, 7, 8]
    >>> a = [1, 2, 2, 3]
    >>> b = [2, 2, 4, 4]
    >>> [i for i in linear_merge(a, b)]
    [1, 2, 2, 2, 2, 3, 4, 4]
    """
    list1 = iter(list1)
    list2 = iter(list2)

    value1 = next(list1)
    value2 = next(list2)

    # We'll normally exit this loop from a next() call raising StopIteration, which is
    # how a generator function exits anyway.
    while True:
        if value1 <= value2:
            # Yield the lower value.
            yield value1
            try:
                # Grab the next value from list1.
                value1 = next(list1)
            except StopIteration:
                # list1 is empty.  Yield the last value we received from list2, then
                # yield the rest of list2.
                yield value2
                while True:
                    yield next(list2)
        else:
            yield value2
            try:
                value2 = next(list2)

            except StopIteration:
                # list2 is empty.
                yield value1
                while True:
                    yield next(list1)

Answer 3

Why stop at two lists?

Here's my generator based implementation to merge any number of sorted iterators in linear time.

I'm not sure why something like this isn't in itertools...

def merge(*sortedlists):

    # Create a list of tuples containing each iterator and its first value
    iterlist = [[i,i.next()] for i in [iter(j) for j in sortedlists]]

    # Perform an initial sort of each iterator's first value
    iterlist.sort(key=lambda x: x[1])

    # Helper function to move the larger first item to its proper position
    def reorder(iterlist, i): 
        if i == len(iterlist) or iterlist[0][1] < iterlist[i][1]:
            iterlist.insert(i-1,iterlist.pop(0))
        else:
            reorder(iterlist,i+1)

    while True:
        if len(iterlist):
            # Reorder the list if the 1st element has grown larger than the 2nd
            if len(iterlist) > 1 and iterlist[0][1] > iterlist[1][1]:
                reorder(iterlist, 1)

            yield iterlist[0][1]

            # try to pull the next value from the current iterator
            try:
                iterlist[0][1] = iterlist[0][0].next()
            except StopIteration:
                del iterlist[0]
        else:
            break

Here's an example:

x = [1,10,20,33,99]
y = [3,11,20,99,1001]
z = [3,5,7,70,1002]

[i for i in merge(x,y,z)]

Answer 4

hi i just did this exercise and i was wondering why not use,

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

pythons sorted function is linear isn't it?

Answer 5

I agree with other answers that extending and sorting is the most straightforward way, but if you must merge, this will be a little faster because it does not make two calls to len every iteration nor does it do a bounds check. The Python pattern, if you could call it that, is to avoid testing for a rare case and catch the exception instead.

def linear_merge(list1, list2):
    merged_list = []
    i = 0
    j = 0

    try:
        while True:
            if list1[i] <= list2[j]:
                merged_list.append(list1[i])
                i += 1
            else:
                merged_list.append(list2[j])
                j += 1
    except IndexError:
        if i == len(list1):
            merged_list.extend(list2[j:])
        if j == len(list2):
            merged_list.extend(list1[i:])
    return merged_list

edit Optimized per John Machin's comment. Moved try outside of while True and extended merged_list upon exception.

Answer 6

Here's my implementation from a previous question:

def merge(*args):
    import copy
    def merge_lists(left, right):
        result = []
        while (len(left) and len(right)):
            which_list = (left if left[0] <= right[0] else right)
            result.append(which_list.pop(0))
        return result + left + right
    lists = [arg for arg in args]
    while len(lists) > 1:
        left, right = copy.copy(lists.pop(0)), copy.copy(lists.pop(0))
        result = merge_lists(left, right)
        lists.append(result)
    return lists.pop(0)

Answer 7

Another generator:

def merge(xs, ys):
    xs = iter(xs)
    ys = iter(ys)
    try:
        y = next(ys)
    except StopIteration:
        for x in xs:
            yield x
        raise StopIteration
    while True:
        for x in xs:
            if x > y:
                yield y
                break
            yield x
        else:
            yield y
            for y in ys:
                yield y
            break
        xs, ys, y = ys, xs, x

Answer 8

According to a note here:

# 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.    

and this link http://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

append is O(1), reverse is O(n) but then it also says that pop is O(n) so which is which? Anyway I have modified the accepted answer to use pop(-1):

def linear_merge(list1, list2):
    # +++your code here+++
    ret = []
    while list1 and list2:
        if list1[-1] > list2[-1]:
            ret.append(list1.pop(-1))
        else:
            ret.append(list2.pop(-1))

    ret.reverse()

    return list1 + list2 + ret

Answer 9

This solution runs in linear time and without editing l1 and l2:

def merge(l1, l2):
  m, m2 = len(l1), len(l2)
  newList = []
  l, r = 0, 0
  while l < m and r < m2:
    if l1[l] < l2[r]:
      newList.append(l1[l])
      l += 1
    else:
      newList.append(l2[r])
      r += 1
  return newList + l1[l:] + l2[r:]