Я реализовал сортировку слиянием в python, но она выдает ошибку «максимальная глубина рекурсии превышена при сравнении»

Question

Я попытался реализовать сортировку слиянием в python, но в функции «слияния», где я проверяю, выполнена ли сортировка, это дает мне максимальную глубину рекурсии, превышенную при ошибке сравнения. Я знаю, что это означает, что она слишком много повторяет функцию, но я понятия не имею, что ее вызывает или как ее исправить. Я пытался настроить некоторые параметры, но ничего не работает. Код и ошибка приведены ниже.

def mergesort(arr, start, end):
    if start > end:
        return

    middle = (start + end) // 2

    mergesort(arr, start, middle)
    mergesort(arr, middle + 1, end)

    return merge(arr, start, end, middle)

def merge(arr, start, end, middle):
    leftCopy = arr[start:middle]
    rightCopy = arr[middle + 1:end]

    leftIndex = 0
    rightIndex = 0

    sortedIndex = start

    while leftIndex < len(leftCopy) and rightIndex < len(rightCopy):
        if leftCopy[leftIndex] > rightCopy[rightIndex]:
            arr[sortedIndex] = leftCopy[leftIndex]
            leftIndex += 1
        else:
            arr[sortedIndex] = rightCopy[rightIndex]
            rightIndex += 1

        sortedIndex += 1

    while leftIndex < len(leftCopy):
        arr[sortedIndex] = leftCopy[leftIndex]
        leftIndex += 1
        sortedIndex += 1

    while rightIndex < len(rightCopy):
        arr[sortedIndex] = rightCopy[rightIndex]
        rightIndex += 1
        sortedIndex += 1

sample = [3, 1, 2]

mergesort(sample, 0, len(sample) - 1)
print(sample)

Ошибка:

Traceback (most recent call last):
  File "mergesort.py", line 43, in <module>
    mergesort(sample, 0, len(sample) - 1)
  File "mergesort.py", line 7, in mergesort
    mergesort(arr, start, middle)
  File "mergesort.py", line 7, in mergesort
    mergesort(arr, start, middle)
  File "mergesort.py", line 7, in mergesort
    mergesort(arr, start, middle)
  [Previous line repeated 995 more times]
  File "mergesort.py", line 2, in mergesort
    if start > end:
RecursionError: maximum recursion depth exceeded in comparison

Answer 1

Ваш базовый случай не распространяется на start==end (что должно быть: список из 1 элемента не может быть не в порядке); в этом случае middle = start, , поэтому первый рекурсивный вызов идентичен текущему - отсюда и бесконечная рекурсия.