Out of range error - merge sort algorithm

Question

I am trying to implement the merge sort algorithm using the following code but am getting a list index is out of range error.

def mergeSort (unSortedList):
if len(unSortedList) == 1 :
    return unSortedList
else:
    midpoint = len(unSortedList)//2
    A = mergeSort (unSortedList[:midpoint] )
    B = mergeSort (unSortedList[midpoint:] )
    i = 0
    j = 0
    C = []
    for k in range(len(unSortedList)):
        if A[i] >= B[j]:
            C.append(A[i])
            if i == len(A):
                C.append(B[j:])
            else:
                i += 1
        elif A[i] < B[j] :
            C.append(B[j])
            if j == len(B):
                C.append(A[i:])
            else:
                j += 1
    return C
testlist = [2,1,4,2,5,6,8,9]
print (mergeSort(testlist))

Any help would be appreciated.

I suggest you extract the merge procedure to an extra function. It will be more readable and clear what it does: merge and sort. — zegkljan
– zegkljan, Commented Jan 20, 2015 at 7:06
You should get your indentation right.. (and post the error). — demented hedgehog
– demented hedgehog, Commented Jan 20, 2015 at 7:31
you're out by one on your conditionals here: if i == len(A): should be if i == len(A) -1: and your next problem is don't add lists like this: C.append(A[i:]) add them like this: C += A[i:] — demented hedgehog
– demented hedgehog, Commented Jan 20, 2015 at 7:45
Also (this looks like homework of some sort).. but for anyone browsing here there's built in list sorting in python e.g. see here wiki.python.org/moin/HowTo/Sorting — demented hedgehog
– demented hedgehog, Commented Jan 20, 2015 at 7:46

zegkljan · Accepted Answer · 2015-01-20 07:35:42Z

1

Here is my version of your mergeSort, with the merge function extracted:

def mergeSort (unSortedList):
    if len(unSortedList) == 1 :
        return unSortedList
    else:
        midpoint = len(unSortedList)//2
        A = mergeSort (unSortedList[:midpoint] )
        B = mergeSort (unSortedList[midpoint:] )
        return merge(A, B)

def merge(a, b):
    i = 0
    j = 0
    c = []
    while True:
        if a[i] < b[j]:
            c.append(b[j])
            j += 1
        elif a[i] >= b[j]:
            c.append(a[i])
            i += 1

        if i == len(a):
            c.extend(b[j:])
            break
        if j == len(b):
            c.extend(a[i:])
            break
    return c

Output:

>>> testlist = [2,1,4,2,5,6,8,9]
>>> mergeSort(testlist)
[9, 8, 6, 5, 4, 2, 2, 1]

Couple of things to note:

Appending a list to a list. When you do C.append(A[j:]) you end up with nested lists. That is because A[j:] always returns a list. You either need to use list addition - C += A[j:] - or call extend - C.extend(A[j:])
Missing breaks. When your i or j got to the end of their lists you correctly appended the rest of the other list but you did not terminate the loop. That is what caused the range error because in the next iteration (which should not happen) you tried to get an item at the index equal to the length of the list which is out of range.

answered Jan 20, 2015 at 7:35

zegkljan

8,4395 gold badges37 silver badges51 bronze badges

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

1 Comment

gounc86 Over a year ago

Great, Thank you ! The list addition method is much simpler.

Collectives™ on Stack Overflow

Out of range error - merge sort algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related