pythonalgorithm

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

Solution

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