Implementing heap sort algorithm in Python receiving recursion error when running

Question

Im trying to implement the heap sort algorithm to sort a list but receiving the following error code: RecursionError: maximum recursion depth exceeded Please let me know if you find any issues I will post my functions and helper functions below as follows:

def heap_sort(A):
    heap_size = _build_max_heap(A)
    for i in range(heap_size // 2, -1):
        A[0], A[i] = A[i],A[0]
        heap_size = heap_size - 1
        _max_heapify(A,heap_size, I)

def _build_max_heap(A):
    heap_size = len(A)
    for i in range(heap_size // 2):
        _max_heapify(A,heap_size, I)
    return heap_size

def _left(I):
    return (2*i)+1

def _right(i):
    return (2*i)+2

def _max_heapify(A, heap_size, i ):
     l = _left(i)
    r = _right(i)
    if l < heap_size and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r < heap_size and A[largest] < A[r]:
        largest = r
    if largest != i:
       A[i], A[largest] = A[largest], A[i]
    _max_heapify(A,heap_size, largest)

Answer 1

Your problem is due to the fact that your _max_heapify function calls itself recursively, and it ALWAYS calls itself, no matter what is passed to it as parameters. For recursion to work, there has to be a condition that becomes true such that the recursive function doesn't call itself. You need to modify your logic so that this is the case...so that there is some condition that at some point halts the recursion by having an execution of _max_heapify that doesn't call itself.