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 right:

Nothing is left to shift, as the gap is now at the left end of the array.

Step 4: We insert the temp_value into the gap, completing our first pass-through:

Next, we begin the second pass-through:

Step 5: In our second pass-through, we temporarily remove the value at index 2. We’ll store this in temp_value. In this case, the temp_value is 7:

Step 6: We compare the 4 to the temp_value:

The 4 is lower, so we won’t shift it. Since we reached a value that is less than the temp_value, this shifting phase is over.

Step 7: We insert the temp_value back into the gap, ending the second pass-through:

We now begin the third pass-through:

Step 8: We temporarily remove the 1 and store it in temp_value:

Step 9: We compare the 7 to the temp_value:

Step 10: The 7 is greater than 1, so we shift the 7 to the right:

Step 11: We compare the 4 to the temp_value:

Step 12: The 4 is greater than 1, so we shift it as well:

Step 13: We compare the 2 to the temp_value:

Step 14: The 2 is greater, so we shift it:

Step 15: The gap has reached the left end of the array, so we insert the temp_value into the gap, concluding this pass-through:

Now, we begin the fourth pass-through:

Step 16: We temporarily remove the value from index 4, making it our temp_value. This is the value 3:

Step 17: We compare the 7 to the temp_value:

Step 18: The 7 is greater, so we shift the 7 to the right:

Step 19: We compare the 4 to the temp_value:

Step 20: The 4 is greater than the 3, so we shift the 4:

Step 21: We compare the 2 to the temp_value. The 2 is less than 3, so our shifting phase is complete:

Step 22: We insert the temp_value back into the gap:

Our array is now fully sorted:

Code Implementation: Insertion Sort

Here’s a Python implementation of Insertion Sort:

Let’s walk through this code step by step.

First, we start a loop beginning at index 1 that runs through the entire array. Each round of this loop represents a pass-through:

Within each pass-through, we save the value we’re “removing” in a variable called temp_value:

Next, we create a variable called position, which will start immediately to the left of the index of the temp_value. This position will represent each value we compare against the temp_value:

As we move through the pass-through, this position will keep moving leftward as we compare each value to the temp_value.

We then begin an inner while loop, which runs as long as position is greater than or equal to 0:

We then perform our comparison; that is, we check whether the value at position is greater than the temp_value:

If it is, we shift that left value to the right:

We then decrement position by 1 to compare the next left value against the temp_value in the next round of the while loop:

If at any point we encounter a value at position that is less than or equal to the temp_value, we can get ready to end our pass-through, since it’s time to move the temp_value into the gap:

The final step of each pass-through is moving the temp_value into the gap:

After all pass-throughs have been completed, we return the sorted array: