Thank you so much, Cameron for the help! I would never figure out the
implicit “return” command by myself.
It’s a lot like a main programme: it exits when you reach the bottom of
the script. Functions exit when you reach the bottom of the function,
but functions return a value, so the placeholder value None
is what is
returned if you don’t supply the value yourself.
Indeed, I’m trying to learn the merge sort function. Below is the complete function. The merge function looks good to me.
To me as well. It can be written more concisely, but the logic all looks
correct.
However, I get lost with the mergesort(). This time, I uncommented the
right = mergesort(L[middle:]) part, and I get totally different
results.
Previously, I only have left=mergesort(L[:middle]), and the function only returns one valid ouptut: L=[1], but with right=mergesort(L[middle:]) added, I get multiple values assigned to left and right varialbe. See below.
intermediate left is [1]
intermediate right is [2]
intermediate left is None
intermediate left is [3]
intermediate right is [4]
intermediate right is None
intermediate left is None
intermediate left is [5]
intermediate right is [6]
intermediate left is None
intermediate left is [7]
intermediate right is [8]
intermediate right is None
intermediate right is None
I know this is what the program is expected to do, i.e., split a list into lists of a single item. However, I don’t understand how the recursion works here. Why one line of code can totally change the recursion order?
It doesn’t change the order. It interleaves a “right branch” into the
previous order.
Let’s look at your “else” branch again:
else:
middle = int(len(L) / 2)
left = mergesort(L[:middle])
print('intermediate left is ',left)
right = mergesort(L[middle:])
print('intermediate right is ',right)
Suppose the last 2 lines were commented out. With only the “left” branch
and starting with a list [1,2,3,4,5,6,7,8]
the merge sort will split
of the left [1,2,3,4]
and call mergesort
on that, which in turn
splits off [1,2]
and calls mergesort on that, which splits off [1]
and calls mergesort on that.
The print()
calls happen after the call and print the result of the
call. So you’d see:
intermediate left is [1]
from the innermost call with the single element list. Because you still
do not have a return
, all the other calls still return None
so they
are hard to tell apart. But you’d get:
intermediate left is None # from [1,2]
intermediate left is None # from [1,2,3,4]
next as the calls returned.
You’re making 1 call to mergesort
every time you halve the list,
until it is short.
With the addition of the “right” branch" there’s a whole subtree of
calls for the right branch between the first line above and the next 2,
and each of those subcalls has its own “left” and “right” branches.
All of this is hard to see in the flat linear printout you’ve got.
Let’s modify the function, entirely to make the calls more obvious.
Change the function header to this:
def mergesort(L, indent=""):
and change the “else” branch like this:
else:
subindent = indent + " "
middle = int(len(L) / 2)
print(indent, 'mergesort left ', L[:middle])
left = mergesort(L[:middle], subindent)
print(indent, 'intermediate left ', L[:middle], '->', left)
print(indent, 'mergesort right ', L[middle:])
right = mergesort(L[middle:], subindent)
print(indent, 'intermediate right ', L[middle:], '->', right)
Here we’re providing a little string-of-spaces to go at the start of the
print()
calls which indents the text. We compute subindent = indent + " "
to pass to the inner calls so that their printouts are indented an
additional 2 spaces.
We’re also doing a print()
before each call to mergesort()
so that
you can see the start of the call as well as its result:
print(indent, 'mergesort left ', L[:middle], '...')
left = mergesort(L[:middle], subindent)
print(indent, 'intermediate left ', L[:middle], '->', left)
Because these lines will usually be separated in the output, we print
the original L[:middle]
list in both print()
s for better context.
When I try that here I get a nice little indented listing showing the
call and the returned result, and making the output ordering clear.
Try this at your end and see what you get, and if the output makes more
sense.
Remember that you’ve still got the merge()
and return together
commented out, so all the calls with longer lists return None
instead
of the merged sublists.
Cheers,
Cameron Simpson cs@cskk.id.au