Earlier (in Part 1), we were introduced to Insertion Sort, and looked at an example to understand it. Here’s the same array example with a nice visualization.
Insertion Sort Visualizer
Initial Pass
Initially, only the first element is considered sorted.
| 10 | 6 | 8 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Pass 1 — Key = 6
Step 1: Choose key 6
Take 6 as the key.
| 10 | 6 | 8 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 2: Compare 6 with 10
Since 10 > 6, 10 must be shifted to the right.
| 10 | 6 | 8 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 3: Shift 10 to the right
10 is shifted one position to the right. The key 6 is being held separately.
| 10 | 10 | 8 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 4: Insert 6
Insert the key 6 at index 1. Now the first two elements are sorted.
| 6 | 10 | 8 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Pass 2 — Key = 8
Step 1: Choose key 8
Take 8 as the key.
| 6 | 10 | 8 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 2: Compare 8 with 10
Since 10 > 8, shift 10 to the right.
| 6 | 10 | 8 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 3: Shift 10
10 is shifted right. Continue comparing the key 8 backwards.
| 6 | 10 | 10 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 4: Compare 8 with 6
Since 6 < 8, stop shifting.
| 6 | 10 | 10 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 5: Insert 8
Insert 8 between 6 and 10. Now the first three elements are sorted.
| 6 | 8 | 10 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Pass 3 — Key = 20
Step 1: Choose key 20
Take 20 as the key.
| 6 | 8 | 10 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 2: Compare 20 with 10
Since 10 < 20, no shifting is needed.
| 6 | 8 | 10 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 3: 20 stays in place
20 is already in the correct position. Now the first four elements are sorted.
| 6 | 8 | 10 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Pass 4 — Key = 14
Step 1: Choose key 14
Take 14 as the key.
| 6 | 8 | 10 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 2: Compare 14 with 20
Since 20 > 14, shift 20 to the right.
| 6 | 8 | 10 | 20 | 14 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 3: Shift 20
20 moves one position to the right. Continue comparing 14 backwards.
| 6 | 8 | 10 | 20 | 20 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 4: Compare 14 with 10
Since 10 < 14, stop shifting.
| 6 | 8 | 10 | 20 | 20 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 5: Insert 14
Insert 14 between 10 and 20. Now the first five elements are sorted.
| 6 | 8 | 10 | 14 | 20 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Pass 5 — Key = 9
Step 1: Choose key 9
Take 9 as the key.
| 6 | 8 | 10 | 14 | 20 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 2: Compare 9 with 20
Since 20 > 9, shift 20 to the right.
| 6 | 8 | 10 | 14 | 20 | 9 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 3: Shift 20
20 shifts to the right.
| 6 | 8 | 10 | 14 | 20 | 20 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 4: Compare 9 with 14
Since 14 > 9, shift 14 to the right.
| 6 | 8 | 10 | 14 | 20 | 20 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 5: Shift 14
14 shifts right. Continue comparing 9 backwards.
| 6 | 8 | 10 | 14 | 14 | 20 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 6: Compare 9 with 10
Since 10 > 9, shift 10 to the right.
| 6 | 8 | 10 | 14 | 14 | 20 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 7: Shift 10
10 shifts right. Continue comparing 9 backwards.
| 6 | 8 | 10 | 10 | 14 | 20 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 8: Compare 9 with 8
Since 8 < 9, stop shifting.
| 6 | 8 | 10 | 10 | 14 | 20 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Step 9: Insert 9
Insert 9 after 8. The array is now fully sorted.
| 6 | 8 | 9 | 10 | 14 | 20 |
| [1] | [2] | [3] | [4] | [5] | [6] |
Main idea: Take the next element as the key, compare it backwards with the sorted portion, shift larger elements right, and insert the key in its correct place.
In the next post, we shall summarise the Insertion Sort algorithm in simple terms, and also analyse its running time.
sri ramanuja seva 
Leave a comment