0

I am trying to create a method for merge sort recursively. I am not so familiar with objects and i am trying to get this right. I know the algorithm works as a stand alone function, but when trying to implement as a class method, i get error.

The problem lies in this two lines of code: 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

And of course is another function append, that appends each time at the self.arr and increases the size by 1 each time an element is appended.

Sachihiro
  • 1,597
  • 2
  • 20
  • 46
  • 1
    You may have to post some of the class definition to answer questions like: What is self? Do you want the method to alter the class or not? Does the class have-a list of data, or is-a list of data? What are you returning? [mcve] – Kenny Ostrom Feb 04 '19 at 23:27
  • Ah, you want left_list and right_list to be new instances of the class. Did you implement the correct overrides for those splices to make that happen? Not enough info. – Kenny Ostrom Feb 04 '19 at 23:33
  • I added some more info about the class itself. What correct overrides? – Sachihiro Feb 04 '19 at 23:38
  • left_list=self.arr[:middle] so you will need to override splicing. https://stackoverflow.com/questions/16033017/how-to-override-the-slice-functionality-of-list-in-its-derived-class But that won't work anyway since self.arr is a regular list, and it will effect other code. It might be smarter to just use the working mergesort function internally. just self.arr = merge_sort(self.arr) – Kenny Ostrom Feb 05 '19 at 00:21
  • This is just for challenging my self, because i have a working algorithm already. – Sachihiro Feb 05 '19 at 00:24
  • click the link in the first comment, please. Too many errors, I can't run this. Once you fix those, you will probably understand the second comment when you get stuck on a certain error message (which you should have included in the original question) – Kenny Ostrom Feb 05 '19 at 16:16

0 Answers0