The Self-Taught Computer Scientist

Introduction to Algorithms
50
# Function call 1
a_list = [3, 6, 9, 2]
left_half = [3, 6]
right_half = [2, 9]
As you can see, 
right_half
is now sorted in function one call’s state. Now, when your algorithm 
comes back to function one’s state, it merges 
left_half
and 
right_half
, which previous recursive 
function calls have already sorted. So, when your algorithm gets to this point and calls its merge code, 
your function has two sorted lists, 
left_half
and 
right_half
, and it just has to merge them to pro-
duce your final, sorted list.
Now, let’s look at the code that merges two lists. Your merge code starts with three variables, which 
you set to 0:
left_ind = 0
right_ind = 0
alist_ind = 0
You use these variables to track the indexes of three lists: 
left_half
, 
right_half
, and 
a_list
.
This code compares each first item in 
left_half
to each first item in 
right_half
and puts the 
smaller number in its correct position in 
a_list
:
while left_ind < len(left_half) and right_ind < len(right_half):
if left_half[left_ind] <= right_half[right_ind]:
a_list[alist_ind] = left_half[left_ind]
left_ind += 1
else:
a_list[alist_ind] = right_half[right_ind]
right_ind += 1
alist_ind += 1
And this code finishes each merge and can also handle a situation in which the two lists you are 
merging are uneven:
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

---

Chapter 4 Sorting Algorithms
51
For example, say you were merging these two lists:
[2], [6, 4]
Python would call your merge code with these variables:
left_ind = 0
right_ind = 0
alist_ind = 0
a_list = [6, 3]
left_half = [6]
right_half = [3]
The expressions 
left_ind < len(left_half)
and 
right_ind < len(right_half)
evaluate to 
True
, 
so you enter your 
while
loop. This code:
left_half[left_ind] <= right_half[right_ind]:
evaluates to 
6 <= 3
, which is 
False
, so this code runs:
if left_half[left_ind] <= right_half[right_ind]:
a_list[alist_ind] = left_half[left_ind]
left_ind += 1
else: