Recursive merge sort - RecursionError: maximum recursion depth exceeded while calling a Python object

Question

I'm very new in programming and Python, so please excuse in advance my lack of knowledge.

I’m trying to implement a recursive merge sort method in a class. However, when I try to run the program I get the following error:

RecursionError: maximum recursion depth exceeded while calling a Python object

This is because of left = self.merge(lst[:middle]) and right = self.merge(lst[middle:]).

Does someone know how this problem could be solved?

def merge(self, lst, reverse=False):

    middle = len(lst) // 2
    left = self.merge(lst[:middle])
    right = self.merge(lst[middle:])

    result = []
    i, j = 0, 0

    if not len(left) or not len(right):
        return left or right

    while i < len(left) and j < len(right):
        if reverse:
            if left[i] > right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        else:
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1

        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break

    return result    


def _merge_sort(self, reverse=False):

    lst = list(self.unsorted_tuple)

    if len(lst) < 2:
        return lst

    return self.merge(lst)

Please format your code and also provide the output you are getting — shuberman, Oct 06 '19 at 17:52
Did you check this - https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it — shuberman, Oct 06 '19 at 18:02
Yes but I don't understand how I can know by how much the recursion limit must be increased.. — Vicgen, Oct 06 '19 at 18:19
Increasing recursion depth will not help you if your function will call itself indefinitely. — gstukelj, Oct 06 '19 at 18:37

gstukelj · Answer 1 · 2019-10-06T18:36:06.600

The problem is that you don't have a properly defined base case. In case of merge sort this would be checking if the passed list is either empty or has only one element (it is trivially true that it is sorted).

I'm guessing you're trying to do this with if not len(left) or not len(right). There's two problems with that. First, I don't think this code does what you think it does, play with it a bit in isolation to see how it behaves. See how I changed it and try to improve it.

Second, the test for the base case must be checked before calling the function again recursively. You never even come to this part because first thing that your merge function does is to call itself again! Here's a standalone merge function (not defined as a class method, I leave this to you):

def merge(lst, reverse=False):

    if len(lst) <= 1: 
        return lst

    middle = len(lst) // 2
    left = merge(lst[:middle])
    right = merge(lst[middle:])

    result = []
    i, j = 0, 0



    while i < len(left) and j < len(right):
        if reverse:
            if left[i] > right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        else:
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1

    if i == len(left):
                result.extend(right[j:])
    if j == len(right):
            result.extend(left[i:])

    return result

I strongly recommend you Aditya Bhargava's Grokking Algorithms - it uses Python and is a good introductory book.

Recursive merge sort - RecursionError: maximum recursion depth exceeded while calling a Python object

1 Answers1