# Insertion Sort

Another basic algorithm for sorting is the Insertion Sort. We can also illustrate this algorithm with playing cards. The Insertion Sort works by sorting cards within a single hand (i.e. a group of seven cards) rather than using two hands like the Simple Sort. In order to do this, we must have a marker to indicate which section of our hand is sorted. The algorithm for this sort is given below:

#### Insertion Card Sort Algorithm

• 1. Get a hand of unsorted cards
• 2. Set a marker for the sorted section after the first card of the hand
• 3. Repeat steps 4 through 6 until the unsorted section is empty
• 4.    Select the first unsorted card
• 5.    Swap this card to the left until it arrives at the correct sorted position.,/li>
• 6.    Advance the marker to the right one card
• 7. Stop
• We begin the sort by placing the marker after the first card in our hand. Then we compare the second card with the first. If the second card is smaller, we swap it with the first. Then we advance our marker to indicate that the sorted section now contains two ordered cards. By repeating this process of swapping an unsorted card into the correct sorted position and advancing our sort marker, we can order the entire hand of cards.

Now let's look at how the Insertion Sort algorithm would work inside a computer. Below is our modified algorithm for sorting a list of numbers.

#### Insertion Sort Algorithm

• 1. Get a list of unsorted numbers
• 2. Set a marker for the sorted section after the first number in the list
• 3. Repeat steps 4 through 6 until the unsorted section is empty
• 4.    Select the first unsorted number
• 5.    Swap this number to the left until it arrives at the correct sorted position
• 6.    Advance the marker to the right one position
• 7. Stop
• 1. First, we give the computer a list of unsorted numbers and store them in an array of memory cells.

2. To begin the sort, the computer divides the sorted and unsorted sections of the list by placing a marker after the first number. To sort the numbers, it will repeatedly compare the first unsorted number with the numbers in the sorted section. If the unsorted number is smaller than its sorted neighbor, the computer will swap them.

3. The first number in the unsorted section is 8, so the computer compares it with the number to the left. Since 8 is greater than 7, these numbers do not need to swapped and the computer simply advances the marker one position. Notice that only one comparison was needed to sort the 8.

4. Now the first number in the unsorted section is 5. 5 is less than 8, so the computer swaps these numbers.

is also less than 7, so the computer swaps these numbers as well.

Now 5 is in the correct order, so the computer advances the marker one position. This time two comparisons and two swaps were needed to sort the number

5. Now the first number in the unsorted section is 2. 2 is less than 8, 7, and 5, so after three comparisons and three swaps, 2 arrives at the correct sorted position, and the computer advances the sort marker.

6. Now the first number in the unsorted section is 4. 4 is less than 8, 7, and 5 but it is not less than 2. This time the computer performs four comparisons and three swaps to put the 4 in the correct order. Only three swaps were needed since the 2 and the 4 did not need to be switched. After these comparisons and swaps, the computer advances the sort marker.

7. Now 6 is the first number in the unsorted section. After three comparisons and two swaps, the computer places the 6 in the correct position between 5 and 7. Notice that the computer did not need to compare the 6 with the 2 or the 4 since it already knows these numbers are less than 5. Once the computer finds a number in the sorted section less than 6, it knows it has found the correct position for 6 and it can advance the sort marker.

8. The final unsorted number is 3. To find the correct position for 3, the computer must compare it with every number in the unsorted section. However, only five swaps are required since the first number (2) is less than 3. After moving 3 to the correct position and advancing the sort marker, the Insertion Sort is complete since the unsorted section is empty.