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