Skip to main content

Section 8.7 Insertion Sort

While Selection sort gets the job done, it is not the only algorithm that can be used for sorting a list. Insertion sort is another relatively straightforward algorithm. It too divides the list into a sorted and unsorted portion, but it sorts cards by shifting each one to the left until it is larger than its neighbor - “inserting” one card at a time into the correct location.
Here is a “human algorithm” for using it to sort cards: 
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
6       Advance the marker to the right one card
7   Stop
To see how the Insertion Card Sort Algorithm works, watch the video below. Pay attention to how the sorted portion is built up. Cards keep swapping until they “find” their resting spot - they do not jump directly to it. Also, note that the sorted portion in this algorithm does not always have the smallest values, just the values that are known to be sorted relative to each other.
Animation used by permission of Virginia Tech

Checkpoint 8.7.2.

How does insertion sort place a newly selected item?
  • It swaps the item left until it reaches its correct position in the sorted portion.
  • It immediately moves the item to the front of the whole list.
  • It discards half the list.
  • It waits until every item has been selected.

Checkpoint 8.7.3.

What is true about insertion sort’s sorted portion?
  • Its items are in order relative to each other, even if they are not the smallest items overall.
  • It is always empty until the final step.
  • It contains only the largest values.
  • It never grows during the algorithm.

Checkpoint 8.7.4.

We do an insertion sort on the list 3, 2, 5, 4, 1. Arrange the blocks below to show the state of the list after each pass of the algorithm.
Note that you may use the same block twice in a row if the current pass does not change the list.
You will not use all of the blocks.
You have attempted of activities on this page.
PrevTopNext