How can I resolve this recursion Error in merge sort?

Question

I am trying to implement merge sort by using only one 1 auxiliary array instead of creating a new array for left and right in recursive routine. because that could lead to extensive cost of extra array creation. And you'll sometimes see Mergesort performing poorly because of that bug.

I am trying to implement merge sort as described in this course here - https://www.coursera.org/learn/algorithms-part1/lecture/ARWDq/mergesort (minute 7 -10).

I am currently facing RecursionError

I have already written the code in python (with huge help from other people in this community). Here it is -

class merge_sort:

    aux_array = []                               

    def __init__(self, data):
        self.data = data
        self.aux_array = [0 for i in range(len(data))]  

    def merge(self, low, mid, high):             

        for k in range(low, high):
            self.aux_array[k] = self.data[k]            

        if( low == high):
            self.data[low] = self.aux_array[low]
            return


        i = low
        j = mid + 1
        for k in range(low, high):
            if(i > mid):
                self.data[k] = self.aux_array[j]        
                j = j + 1
            elif(j > high):
                self.data[k] = self.aux_array[i]        
                i = i + 1
            elif(self.aux_array[i] < self.aux_array[j]):
                self.data[k] = self.aux_array[i]        
                i = i + 1
            else:
                self.data[k] = self.aux_array[j]        
                j = j + 1

        return

    def mergesort(self,low, high):

        if(low < high):
            mid = (high - low)//2
            self.mergesort(low, mid)              
            self.mergesort(mid+1, high)           
            self.merge(low, mid, high)            
        else:
            return

    def start_sort(self):
        high = len(self.data) - 1
        self.mergesort(0, high)


arr = [10, 2, 30, 0, 4]

arr1 = merge_sort(arr)
arr1.start_sort()
print(arr1)

This is the exact error -

Traceback (most recent call last):
  File "new_sorting.py", line 55, in <module>
    arr1.start_sort()
  File "new_sorting.py", line 49, in start_sort
    self.mergesort(0, high)
  File "new_sorting.py", line 42, in mergesort
    self.mergesort(mid+1, high)
  File "new_sorting.py", line 42, in mergesort
    self.mergesort(mid+1, high)
  File "new_sorting.py", line 42, in mergesort
    self.mergesort(mid+1, high)
  [Previous line repeated 993 more times]
  File "new_sorting.py", line 41, in mergesort
    self.mergesort(low, mid)
  File "new_sorting.py", line 39, in mergesort
    if(low < high):
RecursionError: maximum recursion depth exceeded in comparison

Possible duplicate of [What is the maximum recursion depth in Python, and how to increase it?](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it) — DjaouadNM, Jun 06 '19 at 19:04
Currently, it goes up to 997 something in my case as well. I checked with another code in python. But in the context of the above code, with array length of 5, it shouldn't even go up till 30-40 calls. — HARSHIT BAJPAI, Jun 06 '19 at 19:15
I updated my answer to show the questions's code with the fixes commented. — rcgldr, Jun 07 '19 at 04:33

score 0 · Answer 1 · answered Jun 06 '19 at 22:47

0

Math error:

mid = (high - low)//2

The midpoint is actually the mean of the two numbers:

mid = (high + low)//2

Also check for the boundary condition when high = low + 1

answered Jun 06 '19 at 22:47

Prune

76,765
14
60
81

Yes, I checked that. It was due to range function in python actually. It is mentioned in other answers. Thanks for your help! – HARSHIT BAJPAI Jun 07 '19 at 16:59

rcgldr · Accepted Answer · 2019-06-07T04:30:52.113

Fixes noted in comments:

class merge_sort:

    def __init__(self, data):
        self.data = data                            # reference to data
        self.aux_array = [0] * len(data)            # allocate aux_array

    def merge(self, low, mid, high):
        for k in range(low, high+1):                # fix (high+1)
            self.aux_array[k] = self.data[k]
        i = low
        j = mid + 1
        for k in range(low, high+1):                # fix (high+1)
            if(i > mid):
                self.data[k] = self.aux_array[j]
                j = j + 1
            elif(j > high):
                self.data[k] = self.aux_array[i]
                i = i + 1
            elif(self.aux_array[i] < self.aux_array[j]):
                self.data[k] = self.aux_array[i]
                i = i + 1
            else:
                self.data[k] = self.aux_array[j]
                j = j + 1

    def mergesort(self, low, high):
        if(low >= high):
            return
        mid = low + (high - low)//2                 # fix (low + )
        self.mergesort(low, mid)
        self.mergesort(mid+1, high)
        self.merge(low, mid, high)

    def start_sort(self):
        high = len(self.data) - 1
        self.mergesort(0, high)

arr = [10, 2, 30, 0, 4]
#arr1.data will be a reference to arr
arr1 = merge_sort(arr)
arr1.start_sort()
print(arr)                                          # fix (arr not arr1)

How can I resolve this recursion Error in merge sort?

2 Answers2