TechDinoKing TechDinoKing - 7 months ago 19
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

Answer Source
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