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

Answer 1

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)