Teabx - 2 days ago 3
Python Question

# Recursion on a merge sort function is confusing

I understand the basic principle of a recursion, and it is not confusing at all when dealing with simple things such as calculating a number's factorial, which is the most basic usage of a recursion. However, when you start using Recursion in more complicated environments, it starts getting really really confusing for me.

In my case, I wanted to create a function which used the "merge sort" way to sort the items in a list, using a recursion. So i got to work and this is what i came up with at my first attempt (not really I had to fix some typos):

``````def merge_sort(ls):
size = len(ls)
if size <= 1:
return ls
left = merge_sort(ls[:size/2])
right = merge_sort(ls[size/2:])
return merge(left, right)

def merge(left, right):
ls = []
ln1 = len(left)
ln2 = len(right)
length = ln1 + ln2
while length > 0:
if not left:
ls.append(right.pop(0))
length -= 1
elif not right:
ls.append(left.pop(0))
length -= 1
else:
if left[0] < right[0]:
ls.append(left.pop(0))
length -= 1
elif right[0] < left[0]:
ls.append(right.pop(0))
length -= 1
return ls

print merge_sort([8,5,4,6,1])
``````

I clicked run and it worked, but I don't understand why it works. Yes, I created a piece of code which does what was intended to do but I don't understand why.

So "merge_sort" splits the list into two pieces until there is a simple list with a single item. It does this using recursion, and when we get a simple list with a single item it assigns it to a new list, which is left or right. Then i use these 2 new lists in the "merge" function to sort them and merge them together in the right way. So far so good, but what I was expecting when I hit "execute" was for the code to stop here at the first 2 items and print a small list with 2 sorted items. However "merge_sort" keeps going. Even though i believe it should ends after executing:

``````return merge(left, right)
``````

Now this is my question. Why does it return back to the start of "merge_sort" and how does it save the old values without screwing up the new sorted "small list" generated by "merge"? I hope my question makes sense to you.

Thank you for the help guys!