Implementing merge sort by using only one auxiliary array (instead of creating new array recursively)

Question

The basic way of implementing merge sort that is available everywhere is one in which we recursively create new left and right array for each time we perform the split -

https://www.geeksforgeeks.org/merge-sort/ --> [1]

I want to create only one auxiliary array like it is done in the below link-

https://www.coursera.org/learn/algorithms-part1/lecture/ARWDq/mergesort ->[2] - Minute (7 - 10)

The instructor clearly states that at 9:30 in the video - it's important to not create the auxiliary array in the 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.

It does not create new arrays recursively.

Basically, I want to write the code mentioned in the coursera link in python

Here is what I have written so far ->

class merge_sort:

    def __init__(self, data):
        self.data = data

    aux_array = []


    def merge(array, aux_array, low, mid, high):

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

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


    def mergesort(self, data, low, high):
        #high = len(data)
        mid = (high - low)//2
        mergesort(data, low, mid)
        mergesort(data, mid+1, high)
        merge(data, aux_array, low, mid, high)


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


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

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

I am currently getting following error -

TypeError: mergesort() takes 3 positional arguments but 4 were given

I have tried doing this as well -

@classmethod
    def mergesort(cls, data, low, high):
        #high = len(data)
        mid = (high - low)//2
        mergesort(data, low, mid)
        mergesort(data, mid+1, high)
        merge(data, aux_array, low, mid, high)

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

In this case, I get following error -

NameError: name 'mergesort' is not defined

Answer 1

I only have python 2.7. I didn't use a class. Fixes noted in comments.

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

def mergesort(array, aux_array, low, high):     # fix (names)
    if(low >= high):                            # fix (size < 2)
        return                                  # fix (size < 2)
    mid = low + ((high - low)//2)               # fix (low +)
    mergesort(array, aux_array, low, mid)       # fix (names)
    mergesort(array, aux_array, mid+1, high)    # fix (names)
    merge(array, aux_array, low, mid, high)     # fix (names)

def start_sort(array):                          # fix (names)
    aux_array = [0] * len(array)                # fix allocate aux_array
    mergesort(array, aux_array, 0, len(array)-1)

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

start_sort(arr)                                 # fix
print(arr)                                      # fix