A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Insertion Sort in Action

Let’s apply Insertion Sort to the array [4, 2, 7, 1, 3].

We begin the first pass-through by inspecting the value at index 1. This happens to contain the value 2:

Step 1: We temporarily remove the 2 and keep it inside a variable called temp_value. We represent this value by shifting it above the rest of the array:

Step 2: We compare the 4 to the temp_value, which is 2:

Step 3: Because 4 is greater than 2, we shift the 4 to the ...