Python recursive Merge Sort by index

Question

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)
 in 
      1 x = random.sample(range(0, 30), 15)
----> 2 ms(x, 0, 14)

... last 2 frames repeated, from the frame below ...

 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.

user_4593267 · Answer

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

Python recursive Merge Sort by index

1 Answers