I have a question about the Python version of recursive Merge Sort. I completed the basic version, which is only referred by the array, and am now working on the index version. I will sink into the endless loop, but I am not sure where I did wrong. Would you mind sharing some ideas? Thank you in advance.
The successful and non-index version:
def mergesort(x):
# The base case is when the array contains less than 1 observation.
length = len(x)
if length < 2:
return x
else:
# Recursive case:merge sort on the lower subarray, and the upper subarray.
mid = (length) // 2
lower = mergesort(x[:mid])
upper = mergesort(x[mid:])
# merge two subarrays.
x_sorted = merge(lower, upper)
return (x_sorted)
def merge(lower, upper):
nlower = len(lower)
nupper = len(upper)
i, j, k = 0, 0, 0
# create a temp array to store the sorted results
temp = [0] * (nlower + nupper)
# as the lower and upper are sorted, since the base case is the single observation.
# now we compare the smallest element in each sorted array, and store the smaller one to the temp array
# repeat this process until one array is completed moved to the temp array
# store the other array to the end of the temp array
while i < nlower and j < nupper:
if lower[i] <= upper[j]:
temp[k] = lower[i]
i += 1
k += 1
else:
temp[k] = upper[j]
j += 1
k += 1
if i == nlower:
temp[i+j:] = upper[j:]
else:
temp[i+j:] = lower[i:]
return temp
With expected results:
x = random.sample(range(0, 30), 15)
mergesort(x)
[0, 1, 3, 6, 9, 10, 11, 13, 14, 17, 18, 20, 25, 27, 29]
But I will stuck into the endless loop with the index version:
def ms(x, left, right):
# the base case: right == left as a single-element array
if left < right:
mid = (left + right) // 2
ms(x, left, mid)
ms(x, mid, right + 1)
m(x, left, mid, right)
return m
def m(x, left, mid, right):
nlower = mid - left
nupper = right - mid + 1
temp = [0] * (nlower + nupper)
ilower, iupper, k = left, mid, 0
while ilower < mid and iupper < right + 1:
if x[ilower] <= x[iupper]:
temp[k] = x[ilower]
ilower += 1
k += 1
else:
temp[k] = x[iupper]
iupper += 1
k += 1
if ilower == mid:
temp[k:] = x[iupper:right+1]
else:
temp[k:] = x[ilower:mid]
x[left:right+1] = temp
return x
The test data as:
x = random.sample(range(0, 30), 15)
ms(x, 0, 14)
---------------------------------------------------------------------------
RecursionError Traceback (most recent call last)
<ipython-input-59-39859c9eae4a> in <module>
1 x = random.sample(range(0, 30), 15)
----> 2 ms(x, 0, 14)
... last 2 frames repeated, from the frame below ...
<ipython-input-57-854342dcdefb> in ms(x, left, right)
3 if left < right:
4 mid = (left + right)//2
----> 5 ms(x, left, mid)
6 ms(x, mid, right+1)
7 m(x, left, mid, right)
RecursionError: maximum recursion depth exceeded in comparison
Would you mind providing some insights? Thanks.
Your index version uses a confusing convention whereby left is the index of the first element in the slice and right is the index of the last element. This convention requires error-prone +1/-1 adjustments. Your problem is this: mid as computed is the index of the last element in the left half, but you consider mid to be the first element of the right half: a slice of 2 elements is split into one with 0 and one with 2, hence the infinite recursion. You can fix this problem by changing ms(x, mid, right+1) to ms(x, mid+1, right), etc.
Furthermore, retuning m from function ms makes no sense. You should return x if anything at all.
It is much less error prone for right to be the index one past the last element, just like range specifiers in Python. This way there are no confusing +1/-1 adjustments.
Here is modified version:
def ms(x, left, right):
# the base case: right - left as a single-element array
if right - left >= 2:
mid = (left + right) // 2 # index of the first element of the right half
ms(x, left, mid)
ms(x, mid, right)
m(x, left, mid, right)
return x
def m(x, left, mid, right):
nlower = mid - left
nupper = right - mid
temp = [0] * (nlower + nupper)
ilower, iupper, k = left, mid, 0
while ilower < mid and iupper < right:
if x[ilower] <= x[iupper]:
temp[k] = x[ilower]
ilower += 1
k += 1
else:
temp[k] = x[iupper]
iupper += 1
k += 1
if ilower == mid:
temp[k:] = x[iupper:right]
else:
temp[k:] = x[ilower:mid]
x[left:right] = temp
return x
You would invoke as:
x = random.sample(range(0, 30), 15)
ms(x, 0, len(x))