Реализация сортировки слиянием с использованием только одного вспомогательного массива (вместо рекурсивного создания нового массива)

Question

Основной способ реализации сортировки слиянием, доступной везде, - это метод, в котором мы рекурсивно создаем новый левый и правый массив для каждого выполнения разделения -

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

Я хочу создать только один вспомогательный массив, как это сделано в приведенной ниже ссылке -

https://www.coursera.org/learn/algorithms-part1/lecture/ARWDq/mergesort -> [2] - Минут (7 - 10)

Инструктор ясно заявляет, что в 9:30 в видео - важно не создавать вспомогательный массив в рекурсивной процедуре, поскольку это может привести к значительным затратам на создание дополнительного массива.И иногда вы видите, что Mergesort работает плохо из-за этой ошибки.

Он не создает рекурсивные новые массивы.

По сути, я хочу написать код, упомянутый в ссылке на Coursera в python

Вот что я написал до сих пор ->

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)

Я сейчас получаюследующая ошибка -

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

Я тоже пытался это сделать -

@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)

В этом случае я получаю следующую ошибку -

NameError: name 'mergesort' is not defined

Answer 1

У меня есть только Python 2.7. Я не использовал класс. Исправления, отмеченные в комментариях.

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

Answer 2

Отметьте метод сортировки слиянием, где вы вызываете mergesort (...) Вы должны звонить self.mergesort (...)

Это решит ошибку с именем не определено и даст вам ошибку глубины рекурсии вместо этого, поскольку вы рекурсивно вызываете команду mergesort без условия выхода (хотя я предполагаю, что этот шаг был следующим)

Удачи с остальными в этом роде:)

правок, которые я сделал для справки

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