Function to merge sorted lists

[Alex Martelli]

"Edward C. Jones" <edcjones at erols.com> wrote in message
news:3B8F1BE0.6060108 at erols.com...
> Ignacio Vazquez-Abrams wrote:
> > On Thu, 30 Aug 2001, Edward C. Jones wrote:
> >
> >
> >>Has anyone written in C a merge function for sorted Python sequences?
>
> > Sounds interesting, but... and don't take this the wrong way... I can
barely
> > understand what you're trying to say. An example might help.
>
> Here is a Python program that does the same thing:

Yep, but it can be simplified a bit.


> def merge(seq1, seq2):
>      n1 = len(seq1)
>      n2 = len(seq2)
>      i = j = 0
>      merged = []
>      while i < n1 and j < n2:
>          if seq1[i] < seq2[j]:
>             merged.append(seq1[i])
>             i += 1
>          else:
>             merged.append(seq2[j])
>             j += 1

>      if i == n1:
>          tail1 = []
>          tail2 = seq2[j:]
>      else:
>          tail2 = []
>          tail1 = seq1[i:]

This whole if statement is unneded, since seq1[i:]
will "naturally" be [] if i>=len(seq1) [if seq1 is
a list, not another kind of sequence], etc.  So,
you can just remove it and change the following:

>      return merged, tail1, tail2

to:
       return merged+list(seq1[i:])+list(seq2[j:])

(I assume you want to return a single merged list
rather than a tuple of three lists, and that you
don't know whether seq1 and seq2 are lists or other
kinds of sequences -- easy to fix if my assumptions
are off base, of course).


Another interesting approach (probably slower, but
I haven't measured!) might be to make and destructively
use two list-copies of the input sequences:

def mergec(seq1, seq2):
    l1 = list(seq1); l2 = list(seq2)
    merged = []
    while l1 and l2:
        if l1[-1]>l2[-1]:
            merged.append(l1.pop())
        else:
            merged.append(l2.pop())
    l1.reverse(); l2.reverse()
    merged.extend(l1); merged.extend(l2)
    merged.reverse()
    return merged

Note the code is untested (and also based on the
assumption that the result we want is a single
list).  I work from the tail of l1 and l2 as
this is how .pop works, and that's presumably
faster than popping from the front -- but I'm
also appending to the tail of merged at each
step, so merged ends up reversed, which is why
I need the reverse calls before the extend
ones and the final call to reverse at the end.


Alex