Python递归合并按索引排序

Question

我有一个关于递归合并排序的Python版本的问题。我完成了基本版本，它只由数组引用，现在正在处理索引版本。我会陷入无休止的循环，但我不确定哪里做错了。你介意分享一些想法吗？先谢谢你

成功的非索引版本：

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 

预期结果如下：

x = random.sample(range(0, 30), 15)
mergesort(x)
[0, 1, 3, 6, 9, 10, 11, 13, 14, 17, 18, 20, 25, 27, 29]

但我将陷入索引版本的无休止循环：

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

试验数据如下所示：

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

你介意提供一些见解吗？谢谢

Answer 1

索引版本使用了一种混乱的约定，即left是切片中第一个元素的索引，right是最后一个元素的索引。此约定需要易于出错的+1/-1调整。你的问题是：^ {< CD5> }是左半部分中最后一个元素的索引，但是你认为^ {CD5}}是右半部分的第一个元素：2个元素的一个片段被分成0个，2个一个，因此无限递归。您可以通过将ms(x, mid, right+1)更改为ms(x, mid+1, right)等来解决此问题

此外，从函数ms重新调整m没有任何意义。如果有任何问题，您应该返回x

与Python中的范围说明符一样，将right作为超过最后一个元素的索引是不容易出错的。这样就不会有令人困惑的+1/-1调整

以下是修改版本：

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

您将作为以下内容调用：

x = random.sample(range(0, 30), 15)
ms(x, 0, len(x))