Implementing merge sort function in python class, errors

Question

So I have a function defined that works great at doing merge sort on a linear array if it is implemented by its lonesome, but if I put it into a class it bugs out. I think it's a great example of what I don't quite understand about how classes work; possibly in regards to namespace management(?).

See below:

def sort(array):
    print('Splitting', array)
    if len(array) > 1:
        m = len(array)//2
        left = array[:m]
        right = array[m:]

        sort(left)
        sort(right)

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                array[k] = left[i]
                i += 1
            else:
                array[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    print('Merging', array)

arr = [1,6,5,2,10,8,7,4,3,9]
sort(arr)

Produces the expected correct output:

Splitting  [1, 6, 5, 2, 10, 8, 7, 4, 3, 9]
Splitting  [1, 6, 5, 2, 10]
Splitting  [1, 6]
Splitting  [1]
Merging  [1]
Splitting  [6]
Merging  [6]
Merging  [1, 6]
Splitting  [5, 2, 10]
Splitting  [5]
Merging  [5]
Splitting  [2, 10]
Splitting  [2]
Merging  [2]
Splitting  [10]
Merging  [10]
Merging  [2, 10]
Merging  [2, 5, 10]
Merging  [1, 2, 5, 6, 10]
Splitting  [8, 7, 4, 3, 9]
Splitting  [8, 7]
Splitting  [8]
Merging  [8]
Splitting  [7]
Merging  [7]
Merging  [7, 8]
Splitting  [4, 3, 9]
Splitting  [4]
Merging  [4]
Splitting  [3, 9]
Splitting  [3]
Merging  [3]
Splitting  [9]
Merging  [9]
Merging  [3, 9]
Merging  [3, 4, 9]
Merging  [3, 4, 7, 8, 9]
Merging  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

However, I get an error when I attempt to use this function in a class; something to do with namespace managment, I think. See below:

class MergeSort(object):

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

    def sort(self):
        print('Splitting', self.array)
        if len(self.array) > 1:
            m = len(self.array)//2
            left = self.array[:m]
            right = self.array[m:]

            sort(left)
            sort(right)

            i = 0
            j = 0
            k = 0

            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    self.array[k] = left[i]
                    i += 1
                else:
                    self.array[k] = right[j]
                    j += 1
                k += 1

            while i < len(left):
                self.array[k] = left[i]
                i += 1
                k += 1

            while j < len(right):
                self.array[k] = right[j]
                j += 1
                k += 1
        print('Merging', self.array)

x = MergeSort([1,6,5,2,10,8,7,4,3,9])
x.sort()

Produces the error output:

Splitting [1, 6, 5, 2, 10, 8, 7, 4, 3, 9]
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-15-89509f86277e> in <module>()
      1 x = MergeSort([1,6,5,2,10,8,7,4,3,9])
----> 2 x.sort()

<ipython-input-14-2bba116f00ce> in sort(self)
     11             right = self.array[m:]
     12 
---> 13             sort(left)
     14             sort(right)
     15 

NameError: name 'sort' is not defined

My initial instinct, after google searching around was to change subroutines sort(left) and sort(right) by adding prefixive self., but that generates a positional argument error. Would love a comment or two on what it is that I'm not understanding here. And cheers for good votes if my question is not stupid, and down votes if it is.

Your recursive calls to sort should be self.sort. So, it should not be sort(left) and sort(right), but self.sort(left) and self.sort(right). — Tobias Brösamle
– Tobias Brösamle, Commented Jun 8, 2018 at 6:31
@TobiasBrösamle No, that won't work. sort doesn't take an argument (besides self). And, as the OP said in the question, they already tried "adding prefixive self". — abarnert
– abarnert, Commented Jun 8, 2018 at 6:34
@TobiasBrösamle if I do that I get the positional argument error. — reka18
– reka18, Commented Jun 8, 2018 at 6:34
By the way, describing what you wrote instead of showing the code, and then describing the error instead of showing the actual exception, tends to lead to people misunderstanding your question unless they read it very carefully (as seen in the first comment and one of the answers here), and also makes it impossible for people to debug it if you made a simple mistake that might be obvious to others but not to you. — abarnert
– abarnert, Commented Jun 8, 2018 at 6:41

bruno desthuilliers · Accepted Answer · 2018-06-08 07:01:31Z

4

The reason sort(left) doesn't work is that, as you surmised, you can't call a method on self without specifying self. Leaving that off means it looks for a local or global name sort, doesn't find one, and raises a NameError.

The reason self.sort(left) doesn't work is that the API you defined doesn't work that way. Your class takes the list as a constructor argument, and then takes a sort with no arguments, that operates on the list passed in at construction time. So, you have no way to call your own sort with a different array. If you try self.sort(left), you're passing the wrong number of arguments, just like calling abs(1, 2), and you get the same TypeError.

You have to use your API the way you designed it: Create a new MergeSort sorter object with the new list, then call sort on that new object:

leftsorter = MergeSort(left)
leftsorter.sort()
rightsorter = MergeSort(right)
rightsorter.sort()

edited Jun 8, 2018 at 7:01

bruno desthuilliers

78.3k6 gold badges103 silver badges129 bronze badges

answered Jun 8, 2018 at 6:34

abarnert

368k54 gold badges626 silver badges691 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

abarnert Over a year ago

@data83 This is probably about as good a use for classes as you could come up with for this function. It's just that there really isn't any behavior in a merge sort other than the actual sorting, and there isn't any persistent state other than the list itself, so it's not the best example of something to turn into a class. If you can find a function that (maybe after refactoring into a bunch of small functions) has state that needs to persist between function calls, that might be a better candidate. But anyway, it doesn't hurt to try everything, even if some things don't pan out…

abarnert Over a year ago

@EvgenyPogrebnyak His designs modify the list to be sorted. That's a perfectly reasonable thing to do. And they should not return the sorted list if they do so.

reka18 Over a year ago

That is solved by adding return(self.array) to the last line of the sort( ) function within the class.

abarnert Over a year ago

@data83 First, it's not a problem, so it shouldn't be solved. And it's particularly misleading in a recursive function, where the recursive calls have nothing useful to do with the return value.

abarnert Over a year ago

@data83 My point is, I don’t think you want to return the list here at all. The caller still has access to x.array. And the usual Python idiom is that if the main point of a function is to mutate your self or a parameter, you return None, as explained somewhere in the official FAQ, but I’m no longer in front of my computer.

|

reka18 · Accepted Answer · 2018-06-08 08:27:33Z

Replacing the sort(left) and sort(right) components of the sort() function within my class with

leftsorter = MergeSort(left)
leftsorter.sort()
rightsorter = MergeSort(right)
rightsorter.sort()

(Thank you abarnert)

While at the same time removing debugging print statements from the code (thank you Evgany P), and by avoiding reusing a built in function name sort() to avoid confusion, I have a working MergeSort class.

class MergeSort(object):

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

    def merge_sort(self):
        if len(self.array) > 1:
            m = len(self.array)//2
            left = self.array[:m]
            right = self.array[m:]

            leftsorter = MergeSort(left)
            leftsorter.merge_sort()
            rightsorter = MergeSort(right)
            rightsorter.merge_sort()

            i = 0
            j = 0
            k = 0

            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    self.array[k] = left[i]
                    i += 1
                else:
                    self.array[k] = right[j]
                    j += 1
                k += 1

            while i < len(left):
                self.array[k] = left[i]
                i += 1
                k += 1

            while j < len(right):
                self.array[k] = right[j]
                j += 1
                k += 1

x = MergeSort([3,5,6,2,1,4,10,9,8,7])
x.merge_sort()
x.array

Out[ ]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Well done everybody!

Evgeny · Accepted Answer · 2018-06-08 06:34:47Z

-1

You need to call self.sort() within the class.

A larger problem is that none of your function or class method return anything, just prints, are you satisfied with that?

answered Jun 8, 2018 at 6:34

Evgeny

4,5814 gold badges22 silver badges42 bronze badges

8 Comments

abarnert Over a year ago

First, self.sort won't work. Second, if the method mutates the list in-place, it doesn't have to (and, in fact, shouldn't) return anything.

Evgeny Over a year ago

@abarnet, the method can work on the instance variable, but why the function just print? print(sort(x)) is much more explicit

abarnert Over a year ago

Calling self.sort() will just restart sorting the same list you're in the middle of sorting, which will just lead to infinite recursion. It won't sort the left half, which is what the OP is trying to do. I agree that the print is not a great design, but it is useful for debugging purposes, so maybe that's why he did it? But print(sort(x)) is not good either. In Python, functions that mutate objects in-place usually don't return those objects. Just like list.sort() doesn't return the sorted self, it's idiomatic for MergeSort.sort() to not return its sorted self.array.

Evgeny Over a year ago

@abarnert, even for debugging purposes, the function is rather meaningless, if the sorted array is not returned. I do not understand what you mean by the 'function that mutate objects inplace', can you give an example? That may be a class method, but rather pointless for a standalone sort function. When added a return value, the original sort gives wrong recursion, that is probably why the OP seeks a class, but rather wrongly. btw, print(sort(x)) is proper direction for this function, considering you would not call list.sort() a function, but rather a method.

abarnert Over a year ago

I don't know how else to explain "mutates in-place". Maybe try running the OP's (working, non-class-version) code, and doing a print(arr) after sort(arr) and it'll be clear to you.

|

Collectives™ on Stack Overflow

Implementing merge sort function in python class, errors

3 Answers 3

11 Comments

Comments

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

11 Comments

Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related