python - 仅使用一个辅助数组实现合并排序(而不是递归地创建新数组)

Question

实现合并排序的基本方法随处可见，我们每次执行拆分时递归地创建新的左右数组 -

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

我只想创建一个辅助数组，就像在下面的链接中所做的一样-

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

讲师在视频中明确指出在 9:30 - 重要的是不要在递归例程中创建辅助数组，因为这可能会导致创建额外数组的大量成本。由于该错误，您有时会看到 Mergesort 性能不佳。

它不会递归地创建新数组。

基本上，我想用python编写coursera链接中提到的代码

这是我到目前为止写的->

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