implementing/running merge sort in Python

Question

I am writing a program in python and I am trying to implement the merge sort algorithm (and using a function called merge to handle the merge step) and I get an error below. I passed L = [2, 6, 4, 8, 1] to the parameter for merge sort:

>>> L = [2, 6, 4, 8, 1]
>>> mergeSort(L)
Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    mergeSort(L)
  File "H:\CSIS 4014\WinPython-64bit-3.5.3.1Qt5\notebooks\sorts.py", line 19, in mergeSort
    mergeSort(left)
  File "H:\CSIS 4014\WinPython-64bit-3.5.3.1Qt5\notebooks\sorts.py", line 21, in mergeSort
    merge(L, left, right, p, q, r)
  File "H:\CSIS 4014\WinPython-64bit-3.5.3.1Qt5\notebooks\sorts.py", line 24, in merge
    left[len(left)+1] = 999999
IndexError: list assignment index out of range

Below is my source code:

def mergeSort(L) :
    p = 0
    r = len(L) - 1
    if p < r :
        q = math.floor((p + r) / 2)
        left = L[:q]
        right = L[q+1:]
        mergeSort(left)
        mergeSort(right)
        merge(L, left, right, p, q, r)

def merge(L, left, right, p, q, r) :
        left[len(left)+1] = 999999
        right[len(right)+1] = 999999
        i = 1
        j = 1
        k = p 
        for k in range(r) :
                if left[i] <= right[j] :
                        L[k] = left[i]
                        i = i + 1
                elif L[k] == right[j] :
                        j = j + 1

I am trying to use slices for the variables left and right of the subarrays as well as following pseudocode from my textbook. I would appreciate any help!

if left had 5 values (len(left) == 5) it has indexes 0,1,2,3,4. Trying to index into len() + 1 will always be out of range. — TemporalWolf
– TemporalWolf, Commented Sep 14, 2017 at 19:46

user94559 · Accepted Answer · 2017-09-14 19:47:57Z

1

left[len(left)+1] = 999999

This is always going to be an error... you're specifically trying to write to an element that doesn't exist. The last element of the list is at left[len(left) - 1]. Writing to any index beyond that is an error.

Perhaps you meant to append instead?

left.append(999999)

answered Sep 14, 2017 at 19:47

user94559

60.3k6 gold badges108 silver badges107 bronze badges

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

5 Comments

TemporalWolf Over a year ago

I'm still not certain how this helps you merge sort though.

Adam Day Over a year ago

Well the reason why I say: left[len(left)+1] = 999999 right[len(right)+1] = 999999 is because I want to put sentinels at the end of the arrays left and right. Do you think saying left.append(999999) will fix the issue?

user94559 Over a year ago

@TemporalWolf Agreed, I'm not sure what the purpose of the line is in the first place.

user94559 Over a year ago

@AdamDay left.append(999999) will add the number 999999 to the list left. That will certainly resolve your error, but then you'll still have to figure out how to write a merge sort. :-) (My guess is that you'll end up removing this line altogether once you figure out the algorithm.)

TemporalWolf Over a year ago

@AdamDay Adding sentinel values is not required to perform a merge sort.

Collectives™ on Stack Overflow

implementing/running merge sort in Python

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related