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 ...

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

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