TechDinoKing - 1 year ago 50
Python Question

# Python - MergeSort Recursion Error

I made a MergeSort program in python using recursion and I keep getting errors about line 27,line 23,line 18 and a recursion error:

"RecursionError: maximum recursion depth exceeded in comparison" but i don't seem to find any obvious mistake in my code.

``````def merge(list, start, middle, end):
L = list[start:middle]
R = list[middle:end+1]
L.append(99999999999)
R.append(99999999999)
i = j = 0
for k in range(start, end+1):
if L[i] <= R[j]:
list[k] = L[i]
i += 1
else:
list[k] = R[j]
j+=1

def mergesort2(list, start, end):
if start < end:
middle = (start + end)//2
mergesort2(list, start, end)
mergesort2(list, middle+1, end)
merge(list, start, middle, end)

def mergesort(list):
mergesort2(list, 0, len(list)-1)

mylist = [8,23,4,56,75,21,42,10,2,5]
mergesort(mylist)
print(mylist)
``````

Thanks

``````def mergesort2(list, start, end):
if start < end:
middle = start + (end - start)//2
mergesort2(list, start, middle) // notice middle instead of end.
mergesort2(list, middle+1, end)
merge(list, start, middle, end)
``````

You were recursing with the same list without reducing its size, thus it was never reaching the base case.

Edit: Also, middle should be calculated by `start + (end-start)/2`, instead of `(start+end)/2`, to avoid integer overflow errors when using large arrays. It's a good practice.

Edit 2: After analysing the code even more, I found that the output was wrong. I have tried to correct them and this is my code:

``````def merge(start, middle, end):
L = l[:middle]
R = l[middle:]
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] <= R[j]:
l[k] = L[i]
i += 1
else:
l[k] = R[j]
j+=1
k += 1
while i < len(L):
l[k] = L[i]
i += 1
k += 1
while j < len(R):
l[k] = R[j]
j += 1
k += 1

def mergesort2(start, end):
if start < end:
middle = start + (end - start)//2
mergesort2(start, middle)
mergesort2(middle+1, end)
merge(start, middle, end)

def mergesort(l):
mergesort2(0, len(l)-1)

l = [8,23,4,56,75,21,42,10,2,5]
mergesort(l)
print(l)
``````

A few points to be noted:

• Changed the variable name from `list` to `l` to avoid confusion with the keyword `list`.

• There was no use passing the list to every function because it was already declared as a global variable.

• `merge()` had some issues. The loop should actually run from `0` till the length of both the lists are not crossed. If crossed, then just copy the rest of the elements.

• Used proper Python splicing techniques :-p

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download