Merge Sort in Python - RuntimeError: maximum recursion depth exceeded

Question

I am working on merge sort in Python.

I have checked merge function. The arrays are merging fine.

But in the mergeSort Function an error is coming :---

RuntimeError: maximum recursion depth exceeded.

RuntimeError Traceback (most recent call last) in () 63 print(arr[i]), 64 ---> 65 mergeSort(arr,0,n-1) 66 print(" ") 67 print("Sorted Array is")

in mergeSort(arr, l, r) 53 m = l+(r-1)/2 54 mergeSort(arr,l,m) ---> 55 mergeSort(arr,m+1,r) 56 merge(arr,l,m,r) 57

What can be the possible cause of this?

def merge(arr,l,m,r):
    n1 = m-l+1
    n2 = r-m

    L = [0] * n1
    R = [0] * n2

    print("First List")
    for i in range(0,n1):
        L[i] = arr[i+l]
        print(L[i]), 


    print("")
    print("Second List")    
    for j in range(0,n2):
        R[j] = arr[j+m+1]
        print(R[j]),



    #Merging the temp arrays
    i = 0
    j = 0
    k = 0
    print("")
    print("Merged List ---------->")

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            print(arr[k]),
            i+=1
        else:
            arr[k] = R[j]
            print(arr[k]),
            j+=1
        k+=1

    while i<n1:
        arr[k] = L[i]
        i+=1
        k+=1

    while j<n2:
        arr[k] = R[j]
        print(arr[k])
        j+=1
        k+=1

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


arr = [0,12,13,0,1,22]
n = len(arr)

mergeSort(arr,0,n-1)
print(" ")
print("Sorted Array is")
for i in range(0,n-1):
    print(arr[i])

Answer 1

The way m is calculated in mergeSort is wrong(you need to divide in half the whole expression, not only (r-1)). Change it to:

m = (l+(r-1))/2

As you were calculating that incorrectly your method was calling itself recursively over and over again until the maximum method stack depth was exceeded and thus crashing.

Answer 2

• You did the basic mistake .Python is dynamically type language
• Before going to why you got that Run Time RecurssionError ,you need to make one change.
  Instead of m = l+(r-1)/2 write m = (l+r)/2
  Because when you called mergeSort(arr,0,n-1) at that time n-1 is last index value and that's why there is no need of r-1 in m = l+(r-1)/2

Floor Division operator(//) VS Normal division operator(/)

Now coming to the main point why did you got that RecurssionError here is the answer

• When you are doing operation like

m = (l+r)/2

Divide operation will give fractional part i.e. m will be treated as floating variable
so m would never be 0 it would be any floating number say something 0.123 or 2.122 or 1.0025

Because of floating point as m would never be 0 the if condition if l<r: would always true and the mergeSort() function goes into Infinite loop and that's why you got that RunTime RecurssionERROR

You want m as integer and not float so instead of m=(l+r)/2

Write m=(l+r)//2 the floor division operator(//) will give you integer value and your mergeSort() function will not go under Infinite Loop

Your code will get executed this time without any Error just make one change m=(l+r)//2

BUT BUT BUT your merge() function algo is not good it does not give sorted array also the data is lost and something else gets printed

Answer 3

Its because when you are calling mergesort function, you are passing l = 0 and r= lenght of list. And no matter what your calculation going to be in every case you l will be less than r.

 m = l+(r-1)/2