The Self-Taught Computer Scientist

Introduction to Algorithms
44
When your 
while
loop terminates, you insert the current number in 
value
in the correct position 
in the sorted left half of the list:
a_list[i] = value
Let’s take a look at how your insertion sort algorithm works with the following list:
[6, 5, 8, 2]
The first time through your 
for
loop, 
i
is 1, and 
value
is 5:
for i in range(1, len(a_list)):
value = a_list[i]
The following code in bold is 
True
because 
i
> 0 and 6 > 5, so your 
while
loop executes:
while i > 0 and a_list[i - 1] > value:
a_list[i] = a_list[i - 1]
i = i - 1
a_list[i] = value
This code:
while i > 0 and a_list[i - 1] > value:
a_list[i] = a_list[i - 1]
i = i - 1
a_list[i] = value
changes your list from this:
[6, 5, 8, 2]
to this:
[6, 6, 8, 2]
And this code:
while i > 0 and a_list[i - 1] > value:
a_list[i] = a_list[i - 1]
i = i - 1
a_list[i] = value
decrements 
i
by 1. The variable 
i
is now 0, which means your 
while
loop will not execute again:
while i > 0 and a_list[i - 1] > value:
a_list[i] = a_list[i - 1]
i = i - 1
a_list[i] = value

---

Chapter 4 Sorting Algorithms
45
Next, this line of code:
while i > 0 and a_list[i - 1] > value:
a_list[i] = a_list[i - 1]
i = i - 1
a_list[i] = value
changes your list from this:
[6, 6, 8, 2]
to this:
[5, 6, 8, 2]
You’ve sorted the first two items in your list, and all your algorithm has to do now is repeat the 
same process to sort the right half of the list containing 8 and 2.
When to Use Insertion Sort
Like a bubble sort, an insertion sort is stable. Also like a bubble sort, an insertion sort is O(
n**2), 
so it is not very efficient. However, unlike a bubble sort, computer scientists use insertion sorts in 
real- world applications. For example, an insertion sort may be an efficient choice if you have nearly 
sorted data. When a list is sorted or almost sorted, an insertion sort’s time complexity is O(
n), which 
is very efficient.
Say you have the following list:
[1, 2, 3, 4, 5, 7, 6]
As you can see, all the numbers are sorted except for the last two numbers. Because the second 
loop (the 
while
loop) in an insertion sort executes only if two numbers are out of order, sorting this 
nearly sorted list with an insertion sort takes only eight steps, which is linear because the second loop 
has to run only once.
Merge Sort
A merge sort is a recursive sorting algorithm that continually splits a list in half until there are one or 
more lists containing one item and then puts them back together in the correct order. Here is how it 
works. First, you use recursion to continually break your list in half until your original list becomes 
one or more sublists containing only one number (Figure 4.1).
[3]
[6]
[6, 3]
[6, 3, 9, 2]
[9, 2]
[9]
[2]