Insertion Sort: The Idea

Insertion sort is the way most people sort a hand of playing cards:

• Take the first card and hold it in your hand. One card is already sorted.
• Take the next card and insert it into the correct position in your hand, so that the cards in your hand are still sorted.
• Take the next card and insert it into the correct position in your hand, so that the cards in your hand are still sorted.
• Repeat this process until all cards are in your hand and sorted.

You are building up a sorted portion of the cards in your hand, and you insert each new card into the correct position in that sorted portion. Let’s look at how insertion sort works on an array of integers.

Let’s start with the following array: [5, 6, 0, 2, 1, 9, 3].

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  5  │  6  │  0  │  2  │  1  │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘

We can take the first element 5 and consider it to be the sorted portion of the array. Now the second element, 6, is the key that we want to insert into the sorted portion.

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │ █5█ │ ░6░ │  0  │  2  │  1  │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
 sorted─╯

Since 6 is greater than 5, we can just leave it where it is and consider the sorted portion to now be [5, 6], with the key 0:

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │ █5█ │ █6█ │ ░0░ │  2  │  1  │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
  ╰────sorted─╯

The key 0 has to be inserted into the sorted portion [5, 6] so that the sorted portion becomes [0, 5, 6]. We can do this by swapping 0 with 6, and then swapping 0 with 5. Now the sorted portion is [0, 5, 6] with the next key 2:

Before:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │ █5█ │ █6█ │ ░0░ │  2  │  1  │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
  ╰────sorted─╯

         swap 0 and 6
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  5  │ ░0░ │ ░6░ │  2  │  1  │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘

   swap 0 and 5
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │ ░0░ │ ░5░ │  6  │  2  │  1  │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘

After:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │ █0█ │ █5█ │ █6█ │ ░2░ │  1  │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
  ╰──────────sorted─╯

Next, we can repeat the same process for the key 2, so the sorted portion becomes [0, 2, 5, 6] with the next key 1:

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │ █0█ │ █2█ │ █5█ │ █6█ │ ░1░ │  9  │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
  ╰────────────────sorted─╯

Now repeat the process for the key 1, so the sorted portion becomes [0, 1, 2, 5, 6] with the next key 9:

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │ █0█ │ █1█ │ █2█ │ █5█ │ █6█ │ ░9░ │  3  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
  ╰──────────────────────sorted─╯

Here we can just leave 9 where it is because it is greater than 6, so the sorted portion becomes [0, 1, 2, 5, 6, 9] with the next key 3:

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │ █0█ │ █1█ │ █2█ │ █5█ │ █6█ │ █9█ │ ░3░ │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
  ╰────────────────────────────sorted─╯

Finally, we can insert 3 into the sorted portion to get a fully sorted array:

  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │ █0█ │ █1█ │ █2█ │ █3█ │ █5█ │ █6█ │ █9█ │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘