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!

Answer 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)