0

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?

Improve this question
5
  • 1
    why would any class make you do this? are you really supposed to convert this to real code? or are you just supposed to identify the time/space complexity? Commented Feb 18, 2014 at 17:35
  • I can do this by sorted(a+b) also. But I want to use the algorithm provided in the book just for learning purpose Commented Feb 18, 2014 at 17:39
  • since its an analysis of algorithms book ... I would assume it involves analysis not translation to real code... the fact of the matter is you would never ever implement this algorithm in a real world situation Commented Feb 18, 2014 at 17:43
  • What happens if n > m? This pseudocode doesn't include enough preconditions. Commented Feb 18, 2014 at 17:52
  • The pseudo-code in its exact translation is faulty as pointed out by @2rs2ts Commented Feb 18, 2014 at 17:57

4 Answers 4

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Yes this worked. Also below Sabyasachi had given nice solution too. Thanks for the answer.
3

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.

Improve this answer

2 Comments

whoa, didn't notice that one at all. Nice one. +1
Deleted while I debugged, but there it is.
3

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.

Improve this answer

8 Comments

if he is not going to follow the pseudocode there are lots of better ways to do this ... if he is following the pseudocode this solution doesnt work (since it doesnt match the pseudocode )
@JoranBeasley where does it not match the pseudocode.(I might be abstracting it too much)
I think thats exactly it its just different enough that I would say its not a direct translation (Its better than the pseudo code, but not a direct translation)
@JoranBeasley yes I see your point. I didn't read the full line for line to be honest, I just don't feel looping over a list using indices is the python way to do things. Although you can edit it if you want to add indices.
I agree 100% Ill even give you a +1 ... but I dont really think it satisfies what OP is looking for
|
2

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]
Improve this answer

2 Comments

the code does not work when I want to merge two list of different length. try merge_list([1,3,7,5,8],[2,4,6])
there's apparently some implied code here, I'm adding it now

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.