Python中冒泡+归并混合排序实现遇递归深度超限问题求助

我要实现一个结合冒泡排序与归并排序的Python混合排序函数，逻辑是当数组长度超过阈值T时递归执行归并排序，小于等于T时调用冒泡排序来优化原归并排序。但处理长度1000的随机数组时，始终出现「RecursionError: maximum recursion depth exceeded」错误，而原归并排序函数没有这个问题，我疑惑递归次数应该一致，想知道问题出在哪。

以下是编写的代码：

def bubbleSort(arr, l, h):
    isSwapped = False
    size = h - l
    for i in range(size-1):
        for j in range(0, size-i-1):
            if arr[j] > arr[j + 1]:
                isSwapped = True
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if not isSwapped:
            return


def merge(arr, l, m, r):
    size1 = m - l + 1
    size2 = r - m

    l_arr = [0] * size1
    r_arr = [0] * size2

    for i in range(0, size1):
        l_arr[i] = arr[l + i]
    for j in range(0, size2):
        r_arr[j] = arr[m + 1 + j]

    # merge
    i = 0
    j = 0
    k = l

    while i < size1 and j < size2:
        if l_arr[i] <= r_arr[j]:
            arr[k] = l_arr[i]
            i += 1
        else:
            arr[k] = r_arr[j]
            j += 1
        k += 1

    while i < size1:
        arr[k] = l_arr[i]
        i += 1
        k += 1
    while j < size2:
        arr[k] = r_arr[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:
        m = l + (r - l) // 2
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)
    else:
        return


def hybridMergeSort(arr, l, r):
    T = 16
    while l < r:
        if len(arr) <= T:
            bubbleSort(arr, l, r)
            break
        else:
            m = len(arr) // 2
            hybridMergeSort(arr, l, m)
            hybridMergeSort(arr, m + 1, r)
            merge(arr, l, m, r)

问题根源分析 #

1. 无限递归的元凶：while循环
   原归并排序用if l < r做条件判断，满足时才执行递归拆分。但hybridMergeSort里误用了while l < r循环——每次递归调用返回后，外层while会再次检查l < r（此时l和r根本没变），然后重复执行拆分、递归、合并的逻辑，导致递归调用无限重复，直接触发栈深度溢出。

2. 子数组长度判断完全失效
   代码里用len(arr) <= T判断是否触发冒泡排序，但len(arr)是整个数组的长度，不是当前处理的子数组长度（当前子数组长度应为r - l + 1）。这会导致哪怕子数组已经小到阈值以下，依然会走归并递归分支，完全失去混合排序的优化意义。

3. 冒泡排序的区间错误
   bubbleSort里的循环从索引0开始遍历，而不是从参数l开始，这会错误地排序数组的前size个元素，而非指定的[l, h]区间，导致排序结果错误。

修正后的代码 #

修正hybridMergeSort函数 #

def hybridMergeSort(arr, l, r):
    T = 16
    # 用if替代while，避免重复递归
    if l < r:
        current_length = r - l + 1
        # 判断当前子数组长度是否达到阈值
        if current_length <= T:
            bubbleSort(arr, l, r)
        else:
            # 计算当前子数组的中间索引，而非整个数组的中间
            m = l + (r - l) // 2
            hybridMergeSort(arr, l, m)
            hybridMergeSort(arr, m + 1, r)
            merge(arr, l, m, r)

修正bubbleSort函数 #

def bubbleSort(arr, l, h):
    isSwapped = False
    size = h - l + 1
    for i in range(size - 1):
        # 遍历范围限定在[l, h-i]，确保只处理指定子数组
        for j in range(l, h - i):
            if arr[j] > arr[j + 1]:
                isSwapped = True
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if not isSwapped:
            return

修正说明 #

• 将while l < r改为if l < r，和原归并排序逻辑对齐，避免无限递归
• 用current_length = r - l + 1计算当前子数组的实际长度，正确触发冒泡排序的阈值判断
• 修正冒泡排序的遍历起点为l，确保只排序指定区间内的元素
• 拆分中间索引时，用l + (r - l) // 2计算当前子数组的中点，而非整个数组的中点len(arr)//2

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