Insertion Sort

Data Structures & Algorithms, Sorting

Insertion sort operates much like arranging a hand of cards for a game of poker. You probably would want to rearrange the cards in some order before playing. In most cases, the order is ascending. With this assumption, let’s walk through how we will rearrange the unsorted cards [8, 3, 7, 1, 4, 6].

1. Beginning with the first card, 8, we compare it with the next card, 3. Since 3 is smaller, we switch their positions, resulting in [3, 8, 7, 1, 4, 6].
2. Next, we check 8, we find it’s larger than its predecessor, so no changes are needed. The array remains [3, 8, 7, 1, 4, 6].
3. Next, we examine the third card, 7. Comparing it with the cards to its left (3, 8), we find that it belongs between them. We shift 8 to the right and place 7 in its appropriate position, resulting in [3, 7, 8, 1, 4, 6].
4. Now the fourth card, 1, is smaller than all the cards to its left. Therefore, we shift all the cards from one position to the right to make room for 1 at the beginning. This results [1, 3, 7, 8, 4, 6].
5. The fifth card, 4, we can see that it belongs between 3 and 7. So we shift 7 to the right to accommodate 4 in its rightful place, resulting in [1, 3, 4, 7, 8, 6].
6. Lastly, we examine the sixth card, 6. It’s smaller than 7 but larger than 4. We shift 7 to the right and place 6 in its correct position. The final sorted array is [1, 3, 4, 6, 7, 8].