在Python中尝试混合排序算法（冒泡+合并排序）

Question

因此，我的任务是在 python 中创建一个混合排序函数，该函数将利用冒泡排序和合并排序。这个想法很简单；只要超过T值（阈值），合并排序就应该递归运行，而当该值小于或等于T时，就会调用冒泡排序。这稍微优化了原来的合并排序功能。

这是我写的代码：

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)

类似的逻辑适用于混合快速排序算法。我无法弄清楚问题是什么。它总是返回一个错误：RecursionError：超出最大递归深度。使用 mergeSort() 函数本身时不会返回相同的错误。顺便说一句，我正在尝试将它们用于长度为 1000 的随机数组。我感觉递归次数应该是一样的？

我错过了什么吗？

Answer 1

我认为问题出在这里：

m = len(arr) // 2

这会忽略

l

和

r

边界，而是使用 整个 列表的长度。这应该是：

m = l + (l + m) // 2