CODEWITHSUNDEEP
pythonmergesortpython-3.3
Gabriel Nahmias
Gabriel Nahmias

Reputation: 978

IndexError: list index out of range on a Mergesort Operation

I am receiving this error:

Traceback (most recent call last):
  File "Lab1.py", line 24, in <module>
    b = mergesort(a)
  File "Lab1.py", line 19, in mergesort
    left = mergesort(lst[:middle])
  File "Lab1.py", line 21, in mergesort
    return merge(left, right)
  File "Lab1.py", line 12, in merge
    result.append(right[j])
IndexError: list index out of range

... on this code:

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            j += 1
    result.append(right[j])
    return result

def mergesort(lst):
    if len(lst) <= 1:
        return lst
    middle = int(len(lst) / 2)
    left = mergesort(lst[:middle])
    right = mergesort(lst[middle:])
    return merge(left, right)

a = [3,1,2,5,9,6,7]
b = mergesort(a)
print('Input #1: ' + ', '.join(str(x) for x in a))
print('Output #1: ' + ', '.join(str(x) for x in b))

I am using Python 3.3.2.

Upvotes: 0

Views: 706

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1121992

You add 1 to j in the while loop; if j = len(right) - 1 you end up with j = len(right) and that is not a valid index; indices to lists must fall in the range [0, length) (so 0 included, length excluded).

Append before incrementing j, in the loop, and extend the result with the remainder (which are already sorted):

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Slices never raise an IndexError; if the indices fall outside the available values, empty lists are returned. At least one of left[i:] and right[j:] is going to be an empty list.

Demo:

>>> a = [3,1,2,5,9,6,7]
>>> b = mergesort(a)
>>> print('Input #1: ' + ', '.join(str(x) for x in a))
Input #1: 3, 1, 2, 5, 9, 6, 7
>>> print('Output #1: ' + ', '.join(str(x) for x in b))
Output #1: 1, 2, 3, 5, 6, 7, 9

Upvotes: 2

Related Questions