CODEWITHSUNDEEP
pythonsortingmerge
user1661211
user1661211

Reputation: 43

IndexError: pop index out of range (python)

I wrote the following merge sort code:

def merge_sort(self,a):

    #console.log(len(a))
    if len(a) <= 1:
        return a
    left = []
    right = []
    result = []
    middle = int(len(a)/2)
    print middle

    left = a[:middle] #set left equal to the first half of a
    right = a[middle:] #set right equal to the second half of a
    print left
    print right

    left = self.merge_sort(left)
    right = self.merge_sort(right)
    result = self.merge(left, right)

    return result

And then merging code:

def merge(self, left, right):
    result = []
    while len(left) > 0 or len(right) > 0:

        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left.pop(1)    #remove the first element from left

        elif len(left) > 0:
            result.append(left[0])
            left = left.pop(1)    #remove the first element from left

        elif len(right) > 0:
            result.append(right[0])
            right = right.pop(1)  #remove the first element from right

        else:
            result.append(right[0])
            right = right.pop(1)
    return result

I send it the array: a = [12,0,232]

And I get the following outputs (different iterations) and at the last output I get the error, Please help I don't understand exactly why the error is there thank you!:

(1 [12] [0, 232]) (1 [0] [232])

Traceback (most recent call last): ...\Sort_Class.py", line 116, in merge left = left.pop(1) #remove the first element from left IndexError: pop index out of range

Upvotes: 0

Views: 3651

Answers (2)

DSM
DSM

Reputation: 353099

I don't think .pop() does what you think it does. For example, this line:

left = left.pop(1)    #remove the first element from left

doesn't remove the "first" (i.e. zeroth) element from left. .pop(1) is the second element:

>>> a = [10,20,30,40]
>>> a.pop(1)
20
>>> a
[10, 30, 40]

and moreover, if you set a = a.pop(1), then a is no longer a list, but a number:

>>> a = [10,20,30,40]
>>> a = a.pop(1)
>>> a
20

which won't work either. You can replace these with del left[0] or left = left[1:] or simply result.append(left.pop(0)) as noted in an answer just posted. :^) Fixing that reveals another problem, though: your code gets caught in an infinite loop due to the logic here:

    if len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:

If left[0] > right[0], then no branch is taken, nothing happens to either left or right, and you're trapped. If you tweak this to add a right-branch behaviour for this case, your code seems to work:

>>> import random
>>> def check():
...     for length in range(1, 10):
...         for trial in range(10000):
...             v = [random.randrange(-10, 10) for i in range(length)]
...             assert merge_sort(v) == sorted(v)
...     return True
... 
>>> check()
True

Upvotes: 0

Dan D.
Dan D.

Reputation: 74655

There are problems with your code, for example in this selection they are all present:

result.append(left[0])
left = left.pop(1)

This should be:

result.append(left.pop(0))

The problems are:

  1. Python lists use 0-based indexing so left[0] is the first element of a list not left[1] so left.pop(0) pops the first element while left.pop(1) pops the second element
  2. left.pop(1) returns the element popped not the list as it mutates the list. left = left.pop(1) wouldn't make much sense here.
  3. one doesn't need to both fetch the first element by left[0] and then pop it left.pop(0)

Upvotes: 3

Related Questions