求助：请排查我的归并排序代码错误，附报错信息

Alright, let's dig into your merge sort code to fix those bugs one by one:

1. Incorrect index range when calling mergesort #

You called mergesort(A, 0, len(A)), but len(A) returns 5 for your array [5,4,3,2,1]—and since Python uses 0-based indexing, the last valid index is 4. The r parameter in your mergesort function should represent the index of the last element in the subarray, not the length of the array. Fix this by changing the call to:

mergesort(A, 0, len(A)-1)

This prevents out-of-bounds index errors in subsequent recursive calls.

2. Floating-point index issue #

In your mergesort function, the line q=(p+(r-1))/2 returns a floating-point number in Python 3 (e.g., when p=0 and r=4, this gives 1.5). Array indexes must be integers, so use integer division (//) instead to get a whole number:

q = (p + r) // 2

This is the standard way to split the array into left and right subarrays correctly.

3. Wrong sentinel value setup #

Your code tries to set sentinel values with L[i]=65000 and R[j]=65000, but this has two critical issues:

• After the loops that copy elements into L and R, i equals n1-1 and j equals n2-1—so you're overwriting the last element of each list instead of adding a sentinel at the end.
• Manually creating fixed-length lists and looping to copy elements is error-prone. Instead, use Python's slice syntax to copy the subarrays and append the sentinel directly:

  L = A[p:q+1] + [65000]  # Copy left subarray and add sentinel
  R = A[q+1:r+1] + [65000]  # Copy right subarray and add sentinel
  

This eliminates the need for manual index tracking during copying and ensures the sentinel is placed correctly.

Fixed Full Code #

# Merge function
def merge(A, p, q, r):
    L = A[p:q+1] + [65000]
    R = A[q+1:r+1] + [65000]
    i = 0
    j = 0
    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

# Merge sort function
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)

# Test the code
A = [5,4,3,2,1]
mergesort(A, 0, len(A)-1)
print(A)  # Output: [1, 2, 3, 4, 5]

内容的提问来源于stack exchange，提问作者codehopper