A Common-Sense Guide to Data Structures and Algorithms

Insertion Sort in Action

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

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

Setup: 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 #1: We compare the 4 to the temp_value, which is 2:

Step #2: Since 4 is greater than 2, we shift the 4 to the ...