The Self-Taught Computer Scientist

Chapter 4 Sorting Algorithms
43
Here is how to code an insertion sort in Python:
def insertion_sort(a_list):
for i in range(1, len(a_list)):
value = a_list[i]
while i > 0 and a_list[i - 1] > value:
a_list[i] = a_list[i - 1]
i = i - 1
a_list[i] = value
return a_list
You start by defining an 
insertion_sort
function that takes a list of numbers as input:
def insertion_sort(a_list):
Your function uses a 
for
loop to iterate through each item in the list. Then it uses a 
while
loop for 
the comparisons your algorithm makes when adding a new number to the sorted left side of your list:
for i in range(1, len(a_list)):
... 
while i > 0 and a_list[i - 1] > value:
...
Your 
for
loop begins with the second item in your list (index 1). Inside your loop, you keep track 
of the current number in the variable 
value
:
for i in range(1, len(a_list)):
value = a_list[i]
Your 
while
loop moves items from the unsorted right half of your list to the sorted left half. It con-
tinues as long as two things are true: 
i
must be greater than 0, and the previous item in the list must 
be greater than the item that comes after it. The variable 
i
must be greater than 0 because your 
while
loop compares two numbers, and if 
i
is 0, that means your algorithm is at the first item in the list, 
and there is no previous number to compare it to.
while i > 0 and a_list[i - 1] > value:
Your 
while
loop executes only if the number in 
value
is smaller than the previous item in the list. 
Inside your 
while
loop, you move the greater value to the right of your list. Then, your algorithm 
works on finding out where to put the smaller value in the sorted left half of your list. You decrement 
i
so your loop can make another comparison and see if the smaller number needs to move even far-
ther to the left.
while i > 0 and a_list[i - 1] > value:
a_list[i] = a_list[i - 1]
i = i - 1

---