The Self-Taught Computer Scientist

Introduction to Algorithms
48
left_ind += 1
else:
a_list[alist_ind] = right_half[right_ind]
right_ind += 1
alist_ind += 1
while left_ind < len(left_half):
a_list[alist_ind]=left_half[left_ind]
left_ind += 1
alist_ind += 1
while right_ind < len(right_half):
a_list[alist_ind]= right_half[right_ind]
right_ind += 1
alist_ind += 1
Recursion is the key to this algorithm. We will discuss later in the chapter how the second half of 
the algorithm that merges lists works. Let’s walk through the recursive part function call by call. Say 
you start with the list from the beginning of this section:
[6, 3, 9, 2]
The first time you call your 
merge_sort
function, your function creates three variables:
# Function call 1
a_list = [6, 3, 9, 2]
left_half = [6, 3]
right_half = [9, 2]
You pass 
a_list
to your function, and this code creates the other two variables by dividing 
a_list
into a left half and a right half:
mid = len(a_list) // 2
left_half = a_list[:mid]
right_half = a_list[mid:]
Next, your function recursively calls itself and passes in 
left_half
as a parameter:
merge_sort(left_half)
Now, Python creates three more variables:
# Function call 2
a_list = [6, 3]
left_half = [6]
right_half = [3]

---

Chapter 4 Sorting Algorithms
49
The crucial thing to understand is 
left_half
in the first function call and 
a_list
in the second 
function call 
point to the same list. That means when you change 
left_half
in the second function 
call, it changes 
a_list
in the first function call.
Now your code calls itself again, but this time 
left_half
is 
[6]
, and your base case stops further 
recursion.
if len(a_list) > 1:
So, Python moves on to the next line of code:
merge_sort(right_half)
The variable 
right_half
is 
[3]
, so your base case stops your function from calling itself again.
if len(a_list) > 1:
Now Python calls your merge code. Your merge code merges 
left_half
, which is 
[6]
, and 
right_
half
, which is 
[3]
, and saves the result by modifying 
a_list
, which is now sorted:
# Function call 2
a_list = [3, 6]
left_half = [6]
right_half = [3]
As you learned earlier, when you modify 
a_list
in function call 2, you are also changing the var-
iable 
left_half
in function call 1.
Originally, Python’s state during function call 1 looked like this:
# Function call 1
a_list = [6, 3, 9, 2]
left_half = [6, 3]
right_half = [9, 2]
But in function call 2, you modified 
a_list
, which also changed 
left_half
in function call 1. Now 
function call 1’s state looks like this:
# Function call 1
a_list = [3, 6, 9, 2]
left_half = [3, 6]
right_half = [9, 2]
This change is important, because as you know, when you use recursion, Python returns to previous 
states when you hit your base case. As you can see, 
left_half
is now sorted.
Your algorithm then calls itself recursively again, the same process plays out, and 
right_half
gets 
sorted. That means function one’s state now looks like this:

---