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:

images/chapter7/new/optimizing_for_optimistic_scenarios-centered-no-text_Part6.png

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:

images/chapter7/new/optimizing_for_optimistic_scenarios-centered-no-text_Part7.png

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

images/chapter7/new/optimizing_for_optimistic_scenarios-centered-no-text_Part8.png

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

Get A Common-Sense Guide to Data Structures and Algorithms now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.