归并排序伪代码转Python算法遇问题，请求排查代码错误

原伪代码（1索引） #

MergeSort(A[1 .. n]):
   if n > 1
      m ← ⌊n/2⌋
      MergeSort(A[1 .. m])
      MergeSort(A[m + 1 .. n])
      Merge(A[1 .. n], m)

Merge(A[1 .. n], m):
   i ← 1; j ← m + 1
   for k ← 1 to n
      if j > n
         B[k] ← A[i]; i ← i + 1
      else if i > m
         B[k] ← A[j]; j ← j + 1
      else if A[i] < A[j]
         B[k] ← A[i]; i ← i + 1
      else
         B[k] ← A[j]; j ← j + 1
   for k ← 1 to n
      A[k] ← B[k]

你的Python代码 #

def mergeSort(arr):
    n = len(arr)
    if n > 1:
        m = n//2
        mergeSort(arr[:m])
        mergeSort(arr[m:])
        merge(arr, m)

def merge(arr, m):
    n = len(arr)
    i = 0
    j = m
    b = [0] * n
    
    for k in range(n):
        if j >= n:
            b[k] = arr[i]
            i += 1
        elif i > m-1:
            b[k] = arr[j]
            j += 1
        elif arr[i] < arr[j]:
            b[k] = arr[i]
            i += 1
        else:
            b[k] = arr[j]
            j += 1
    for k in range(n):
        arr[k] = b[k] 

核心问题分析 #

伪代码中MergeSort(A[1..m])是直接操作原数组的子区间，但你的代码里mergeSort(arr[:m])和mergeSort(arr[m:])是对原数组做切片操作——切片会生成新的列表副本。递归排序的是这些副本，排序结果不会同步回原数组，导致原数组的前后两部分始终是未排序状态，最后调用merge时，合并的还是未排序的原数组，自然得不到正确结果。

修正方案 #

方案1：返回排序后的新数组（Python风格） #

这种方式更符合Python的习惯，不修改原数组，而是返回排序后的新数组：

def mergeSort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    m = n // 2
    # 分别排序左右子数组
    left_sorted = mergeSort(arr[:m])
    right_sorted = mergeSort(arr[m:])
    # 合并两个有序子数组
    return merge(left_sorted, right_sorted)

def merge(left, right):
    result = []
    i = j = 0
    # 交替选取左右数组中较小的元素
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 添加剩余元素
    result.extend(left[i:])
    result.extend(right[j:])
    return result

方案2：通过索引原地修改原数组（贴近伪代码逻辑） #

这种方式和伪代码思路一致，通过传递索引来操作原数组的子区间，实现原地排序：

def mergeSort(arr):
    n = len(arr)
    _mergeSort(arr, 0, n - 1)

# 辅助函数，操作arr[left..right]区间
def _mergeSort(arr, left, right):
    if left < right:
        mid = (left + right) // 2
        _mergeSort(arr, left, mid)
        _mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right)

def merge(arr, left, mid, right):
    # 拆分左右子数组
    left_len = mid - left + 1
    right_len = right - mid
    left_arr = arr[left:left+left_len]
    right_arr = arr[mid+1:mid+1+right_len]
    
    i = j = 0
    k = left
    # 合并到原数组的对应位置
    while i < left_len and j < right_len:
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1
    # 处理剩余元素
    while i < left_len:
        arr[k] = left_arr[i]
        i += 1
        k += 1
    while j < right_len:
        arr[k] = right_arr[j]
        j += 1
        k += 1

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