Python - MergeSort Recursion Error

Question

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

Have you tried searching for the error? https://stackoverflow.com/questions/3323001/maximum-recursion-depth — Peter Wood, Dec 13 '16 at 10:32
I tried searching for the error before I posted this question but I didn't get what i was looking for. — TechDinoKing, Dec 13 '16 at 12:27

Shubham · Accepted Answer · 2016-12-13T10:50:42.140

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

Python - MergeSort Recursion Error

1 Answers1