Merge sort "maximum recursion depth exceeded in comparison " [duplicate]

Question

I want to code merge sort in Python 3.

Here is my code:

import math

def Merge(array,start,mid,end):
    n1 = mid - start +1
    n2 = end - mid
    i = 0
    j = 0
    left = [None] * n1
    right = [None] * n2
    inv = 0
    for i in range(0,n1):
        left[i] = array[start + i - 1]
    for j in range(0,n2):
        right[j] = array[mid + j]

    left.append(math.inf)
    right.append(math.inf)
    new_list = []
    for k in range(0,end):
        if left[i] <= right[j]:
            array[k] = left[i]
            i+=1
        elif left[i] > right[j]:
            array[k] = right[j]
            j+=1

def MergeSort(array,start,end):
    if len(array) <= 1:
        return array
    mid = math.ceil((start + end)/2)
    MergeSort(array,start,mid)
    MergeSort(array,mid+start,end)
    Merge(array,start,mid,end)


stuff = [1, -5, 17, 32, 6] 
MergeSort(stuff, 0, len(stuff))
print(stuff)

I tested first function(Merge) it works as it should. But I have a problem with the recursion. I cannot figure out where is the problem. The error is "maximum recursion depth exceeded in comparison".

Minimal, complete, verifiable example applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. Your posted code defines two functions and quits without any calls at all. — Prune
– Prune, Commented Aug 14, 2018 at 17:44
Insert this line in your MergeSort function (as the first line) and see for yourself whats going on print("Start %i End %i" % (start,end)) . This has nothing to do with recursion limit — Some Guy
– Some Guy, Commented Aug 14, 2018 at 17:49
Seems for k in range(0,end): should be for k in range(start,end): — MBo
– MBo, Commented Aug 14, 2018 at 17:52

Prune · Accepted Answer · 2018-08-14 17:51:11Z

3

You have no functional exit from MergeSort. The length of the list never changes, as you pass the entire list on every call. If you start with 5 elements in the list, then len(array) is always 5. As a result, you get down to the left-hand base item (one element) and continue to hammer on that one element forever.

Try checking the bounds, such as

if end - start <= 1:

This will at least get you to the next execution problems.

See this lovely debug blog for help. If nothing else, learn to put in useful print statements to trace data and control flow.

answered Aug 14, 2018 at 17:51

Prune

78k14 gold badges63 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user2699 Over a year ago

Upvoting for the blog post on debugging.

Prune Over a year ago

That blog is a standard "favorite" on Stack Overflow. I've had it bookmarked for at least a year.

Collectives™ on Stack Overflow

Merge sort "maximum recursion depth exceeded in comparison " [duplicate]

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related