CODEWITHSUNDEEP
pythonsorting
Mahadeva
Mahadeva

Reputation: 1637

Implementing Merging of List in Python

I am writing a simple program in Python that has to merge two list. I have taken the following pseudocode from An Introduction to Analysis of Algorithm.

Algorithm For Merging two list

Now I have written following Program in Python.

def merge_list(a,b):
    a,b = sorted(a),sorted(b)
    p1,p2,i = 0,0,0   #python indices start from 0
    c = [0 for x in range(len(a)+len(b))]
    while i<(len(a)+len(b)):

        if a[p1] <= b[p2]:
            c[i] = a[p1]
            p1 = p1 + 1
        else:
            c[i] = b[p1]
            p2 = p2 + 1
        i += 1

    return c
res = merge_list([1,3,5],[2,4,6])

Now I am getting Error with IndexError: list index out of range . Please correct me what I am doing wrong here?

Upvotes: 0

Views: 420

Answers (4)

Aaron Hall
Aaron Hall

Reputation: 395015

You're incrementing p1 beyond a's range.

You need a check for if you've reached the end of one of the lists.

def merge_list(a,b):
    a,b = sorted(a),sorted(b)
    p1,p2,i = 0,0,0   #python indices start from 0
    c = []
    # first two conditions here are implied.
    while p1 < len(a) and p2 < len(b) and i < (len(a)+len(b)):
        if a[p1] <= b[p2]:
            c.append(a[p1])
            p1 += 1
        else:
            c.append(b[p2])
            p2 += 1
    if p1 >= len(a): # implied 
        while p2 < len(b):
            c.append(b[p2])
            p2 += 1
            i += 1
    if p2 >= len(b): # implied
        while p1 < len(a):
            c.append(a[p1])
            p1 += 1
            i += 1
    i += 1
    return c

res = merge_list([1,3,5,7],[2,4,6,8,10])
print res

prints 

[1, 2, 3, 4, 5, 6, 7, 8, 10]

Upvotes: 2

Guy
Guy

Reputation: 624

That code doesn't look very pythonic at all. Do something like this. 

def merge(a,b):
    c=[]
    while a and b:
            if a[0]<b[0]:
                 c+=a[:1]
                 a=a[1:]
            else:
                 c+=b[:1]
                 b=b[1:]
    return c+a+b

Explanation:It creates a new list c. while a and b checks if both a and b have elements in them. Then it checks which of the first elements is smaller and adds that to c(Note that a[:1] is equivalent to [a[0]] and removes the element from the original list by reassigning it. Finally when it comes out of the loop, one of the lists is empty so the return actually either returns c+a or c+b which is quite intuitively what you would expect merge to return.

Upvotes: 3

2rs2ts
2rs2ts

Reputation: 11026

As others have pointed out, you mixed up p1 and p2. But you also have to check for an empty list, and you also have to account for the possibility that the inputs do not have the same length. This algorithm does not list all of its preconditions, namely, n must be less than or equal to m for it to work as written. So let's take care of that.

>>> def merge_list(a,b):
    a,b = sorted(a),sorted(b)
    if len(a) > len(b):
        a,b = b,a
    p1,p2,i = 0,0,0   #python indices start from 0
    c = [0 for x in range(len(a)+len(b))]
    while i<(len(a)+len(b)):

        if p1<len(a) and p2<len(b) and a[p1] <= b[p2]:
            c[i] = a[p1]
            p1 = p1 + 1
        elif p2<len(b):
            c[i] = b[p2]
            p2 = p2 + 1
        i += 1

    return c

>>> merge_list([1,3,5,7,9],[2,4,6,8])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> merge_list([1,3,5],[2,4,6,7])
[1, 2, 3, 4, 5, 6, 7]

The first three lines of this revised are not strictly from the pseudocode, but otherwise this is a 1-to-1 pairing with the pseudocode.

Note that Sabyasachi's answer is a lot more pythonic and would generally be preferred.

Upvotes: 4

Xycor
Xycor

Reputation: 63

Typo. After the else statement you use p1 to index b

else:
    c[i] = b[p1]
    p2 = p2 + 1

Should be:

else:
    c[i] = b[p2]
    p2 = p2 + 1

Looking at this problem again you also need the length check from Aaron's answer below.

Upvotes: 3

Related Questions