The Self-Taught Computer Scientist

a_list[alist_ind] = right_half[right_ind]
right_ind += 1
alist_ind += 1
Now your variables look like this:
left_ind = 0
right_ind = 1
alist_ind = 1
a_list = [3, 3]
left_half = [6]
right_half = [3]
The next time through your 
while
loop, the following code does not execute because 
right_ind
is not less than the length of 
right_half
:
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

---

Introduction to Algorithms
52
Next, this code executes because 
left_ind
is less than the length of 
left_half
:
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
Now your variables look like this:
left_ind = 1
right_ind = 1
alist_ind = 2
a_list = [3, 6]
left_half = [6]
right_half = [3]
Your list is now sorted, and your merge is complete.
When to Use Merge Sort
A merge sort is an example of a divide- and- conquer algorithm. A divide- and- conquer algorithm is one 
that recursively breaks a problem into two or more related subproblems until they are simple enough 
to solve easily. In a merge sort, you break down a list into sublists until each sublist has only one item, 
making it simple to solve because a list with one item is sorted by definition. A merge sort’s run time is 
O(
n * log n) because while splitting the initial list into sublists is logarithmic, the algorithm requires 
linear time to handle each item in the sublists as it merges them. With log- linear time complexity, a 
merge sort is one of the most efficient sorting algorithms and widely used by computer scientists. For 
example, Python uses merge sort in its built- in sorting algorithms, which you will learn about shortly. 
Like bubble sort and insertion sort, a merge sort is also stable.
You can also apply the merge concept from a merge sort to situations other than sorting. For 
example, imagine you are in a classroom with 50 students. Every student has a random amount of 
change in their pocket, up to $1. What is the best way to add up all of the change? The first answer 
you may think of is to have the professor walk up to every student and ask them how much change 
they have and add it all up. That solution is a linear search, and its run time is O(
n). Instead of 
performing a linear search, it is more efficient to have the students merge themselves. Here is how it 
works: every student will pick the student next to them, take their change, and add it to theirs (and 
remember the new total). The students without any change then leave the room. You then repeat this 

---