# Ex16 figuring out merge_sort

I am trying to figure out how to make the merge_sort algorithm with the use of double linked lists, but I am bumping into an error that says I need to use an extra positional argument (which I think is self).

This is the code:

Sorter

``````from ex16 import ex14

def merge_sort(numbers):

#if length of m <_ 1 then
#return m

if numbers.count() <= 1:
return numbers

#var left := empty list
#var right := empty list

#for each x with index i in m do
#if i < (length of m)/2 then
#else
nodes = numbers.begin
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
while nodes:
if numbers.begin.data >= numbers.count():
left_list.create(numbers.begin)
else:
right_list.create(numbers.begin)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
nodes = nodes.next

# left := merge_sort(left)
leftmerged = merge_sort(left_list)
# right := merge_sort(right)
rightmerged = merge_sort(right_list)
#return merge(left, right)
return merge(leftmerged, rightmerged)

def merge(left, right):

#var result := empty list
result = []

#while left is not empty and right is not empty do:
#if first (left) <_ first(right) then:
#append first(left) to result
#left := rest(left)
#else:
#append first(right) to result
#right := rest(right)
while left > 1 and right > 1:
if left[0] <= right[0]:
result.append(left[0])
left = left[1:]
else:
result.append(right[0])
right = right[1:]

#while left is not empty do:
#append first(left) to result
#left := rest(left)
while left > 1:
result.append(left[0])
left = left[1:]

#append first(right) to result
# right := rest(right)
while right > 1:
result.append(right[0])
right = right[1:]

#return result
return result
``````

``````class DoubleLinkedListNode(object):

def __init__(self, data):
self.data = data
self.next = None
self.prev = None

def __init__(self):
self.begin = None
self.end = None``````

test

``````from ex16 import sorting
from ex16 import ex14
from random import randint

max_numbers = 30

def test_merge_sort():
numbers = random_list(max_numbers)

sorting.merge_sort(numbers)

assert is_sorted(numbers)
``````

The code that is not working is marked with arrows.

I get the following error:

TypeError: create() missing 1 required positional argument: ‘obj’

I am guessing that the extra argument it needs is the self, which I did not need to use when I was working in the module itself. However, if I type in self, I get the following error:

NameError: name ‘self’ is not defined

So what am I missing here?

This is kind of an interesting one. I’ll give you just a hint:

``````left_list = ex14.DoubleLinkedList
``````

Now `left_list` is the same thing as `ex14.DoubleLinkedList`, right? So what exactly is it?

Haha. Ok thank you, I’ve figured out the problem. However, I could not give en exact answer to your question.

``left_list = ex14.DoubleLinkedList``

This definetly made something, otherwise it would error. But what it made? I don’t know.

PS: Do you have any tips for printing out something in a test? I don’t know how to print out something which I suspect is being problematic.

`left_list` becomes a synonym for the class. After you’ve done this you could do `my_list = left_list()` to get an instance. They like to say that classes are “first-class objects” in Python. It means that you can pass classes around like anything else.

I don’t have time now to read through the rest of your post. Will do later if I can.

Allright, And what was the practical difference between a synonym and an instance again?

Also, I checked the cheatsheet and saw that I was way of track, so I deleted the rest of the post and started working with the cheatsheet. I didn’t totally copypaste, but tried to adjust what I already had.

So the cheatsheet looks like this:

So what do these two lines of code do?

``````    if left == None: return right
if right == None: return left
``````

Where do they return the right and the left? Shouldn’t the leftover lefts and rights be added to the result? Or are they?

Ok, synonym was a bad word choice. When you assign a class to a variable, that variable contains the class, not an instance of the class.

Well, the returned value ends up in the line `result.next = merge(left, right.next)` (or the other way around) one step up in the recursive call chain.

Are you using pytest? I believe it has a an option to not hide output from your test functions.

A free service run by Zed A. Shaw for learncodethehardway.org.