CLRS Merge Sort Index out of bounds

Why does this code fail to sort the random array?

I've tried fiddling with the indexes a bit but to no avail. I tried making an adjustment to compensate for Pythons zero-based indexing but this did not result in a sorted array. I've implemented the algorithm from the book on page 31 (3rd Edition).

import numpy as np
import math

X = np.random.randint(0,10,10).tolist()

def merge(a, p, q, r):
    n1 = q - p + 1
    n2 = r - q

    L = [0] * (n1 + 1)
    R = [0] * (n2 + 1)

    for i in range(0, n1):
        L[i] = a[p + i - 1]

    for j in range(0, n2):
        R[j] = a[q + j]

    L.append(math.inf)
    R.append(math.inf)

    i = 0
    j = 0

    for k in range(p, r):
        print(k)
        if L[i] <= R[j]:
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

def mergesort(a, p, r):
    if p < r:
        q = (p + r)//2
        mergesort(a, p, q)
        mergesort(a, q+1, r)
        merge(a, p, q, r)

print("Before: {}\n".format(X))
mergesort(X,0,10)
print("After: {}".format(X))

Your code appears to assume one-indexed arrays but Python uses zero-indexing. For example, in your merge function you have:

for i in range(0, n1):
    L[i] = a[p + i - 1]

If you call your sort with p = 0, then for i = 0 you are trying to access a[-1] (the last element), which is not what you want. Also, your merge loop:

for k in range(p, r):

doesn’t include the element at index r (if you meant r to be the last index).

Here is an updated version of your code to fix the indexing:

import math
import numpy as np

# Create a random list of 10 integers
X = np.random.randint(0, 10, 10).tolist()

def merge(a, p, q, r):
    n1 = q - p + 1
    n2 = r - q

    L = [0] * n1
    R = [0] * n2

    # Copy data into temporary lists (0-indexed)
    for i in range(n1):
        L[i] = a[p + i]
    for j in range(n2):
        R[j] = a[q + 1 + j]

    # Append sentinel values
    L.append(math.inf)
    R.append(math.inf)

    i = 0
    j = 0

    # Merge the temporary arrays back into a[p..r]
    for k in range(p, r + 1):
        if L[i] <= R[j]:
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

def mergesort(a, p, r):
    if p < r:
        q = (p + r) // 2
        mergesort(a, p, q)
        mergesort(a, q + 1, r)
        merge(a, p, q, r)

print("Before: {}\n".format(X))
# Call mergesort with last index = len(X)-1
mergesort(X, 0, len(X) - 1)
print("After: {}".format(X))