python - 递归归并排序的类方法

Question

我正在尝试创建一种递归合并排序的方法。我对对象不太熟悉，我正在努力做到这一点。我知道该算法作为一个独立的函数工作，但是当试图作为一个类方法来实现时，我得到了错误。

问题在于这两行代码： left_list = left_list.merge_sort() right_list = right_list.merge_sort()

class Lists(object):
    def __init__(self):
        self.capacity = 8
        self.arr = [None] * capacity
        self.size = 0

    def merge_sort(self):
        if self.size <= 1:
            return self.arr

        middle = self.size // 2
        left_list = self.arr[:middle]
        right_list = self.arr[middle:]
        left_list = left_list.merge_sort()
        right_list = right_list.merge_sort()
        return list(self.merge(left_list, right_list))


    def merge(self, left_half, right_half):
        res = []
        while len(left_half) != 0 and len(right_half) != 0:
            if left_half[0] < right_half[0]:
                res.append(left_half[0])
                left_half.remove(left_half[0])
            else:
                res.append(right_half[0])
                right_half.remove(right_half[0])
        if len(left_half) == 0:
            res = res + right_half
        else:
            res = res + left_half
        return res

当然还有另一个函数 append，它每次都在 self.arr 处追加，并且每次追加元素时将大小增加 1。

标签： pythonsortingrecursion