Insertion sort

Prerequisites

• Arrays and zero-based indexing.
• A while loop with two conditions joined by &&.
• Big-O notation (see Complexity analysis), and ideally Bubble sort.

The analogy

How it works

Start with one insertion by hand

Take [4, 2, 5, 1]. The prefix [4] is already sorted. At each step, guess first, then open "Check".

Count the work

Add up what happened on [4, 2, 5, 1].

• Comparisons. Predict the total.
  Check

  1 + 1 + 3 = 5 comparisons.

• Shifts. Now count the pairs that are in the wrong order: (4,2), (4,1), (2,1), (5,1). Predict: how does that number compare with the shifts?
  Check

  Both are 4. Every shift fixes exactly one out-of-order pair.

The rule in plain words

Take the next number as the key. While the number to its left is bigger, shift that number one slot right. Drop the key into the gap.

That is one insertion. The sorted prefix is now one longer. Repeat until the prefix is the whole array.

The code

Read this code after you have done one insertion by hand. It will make more sense.

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];                      /* save it before shifting */
        int j = i - 1;
        while (j >= 0 && a[j] > key) {   /* strict > keeps it stable */
            a[j + 1] = a[j];                 /* shift right */
            j--;
        }
        a[j + 1] = key;                      /* drop into the gap */
    }
}

flowchart TD
  A["key = a[i], j = i - 1"] --> B{"j >= 0 and a[j] > key ?"}
  B -->|yes| C["Shift: a[j+1] = a[j], j = j - 1"]
  C --> B
  B -->|no| D["Insert: a[j+1] = key"]
  D --> E{"More elements?"}
  E -->|yes| A
  E -->|no| F["Done: the array is sorted"]
          

How fast is it?

On reversed input, key $i$ shifts past all $i$ numbers before it. Adding them up gives the worst case:

In general the cost is $\Theta(n + I)$, where $I$ is the number of inversions. Sorted input has $I = 0$, so it takes $O(n)$.

Common mistakes

• Shifting before saving a[i] into key, which overwrites the number you are inserting.
• Testing a[j] > key before j >= 0, which reads past the start of the array.
• Using >= instead of >, which moves equal items past each other and breaks stability.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• The prefix is always sorted, because each key is dropped exactly where it fits among the numbers already there.
• The worst case is $O(n^2)$ because on reversed input key $i$ shifts past all $i$ numbers before it, $\frac{n(n-1)}{2}$ in total.
• The best case is $O(n)$ because on sorted input every key stops after one comparison.
• Shifts equal inversions because each shift moves a bigger number past the key, fixing exactly one out-of-order pair.
• It is stable because the loop stops at an equal value, so the key never jumps over it.
• Extra space is $O(1)$ because only the key is stored outside the array.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is insertion sort like sorting a hand of cards?
   Sample answer

   You pick up one card at a time and slide it left past bigger cards until it fits. The cards in your hand stay sorted the whole time.

2. Walk through [4, 2, 5, 1]. What happens when the key is 1?
   Sample answer

   The prefix is [2, 4, 5]. All three are bigger than 1, so they shift right and 1 lands at the front, giving [1, 2, 4, 5].

3. Why does the code save a[i] in key before the loop?

   A good answer says what the first shift does to a[i].

   Sample answer

   The first shift writes a[i-1] into a[i], which would destroy the number we're inserting. Saving it first keeps it safe until we drop it in the gap.

4. So what is insertion sort, in one sentence?
   Sample answer

   It grows a sorted prefix by taking the next element and shifting bigger elements right until the element fits.

5. Why is the running time tied to the number of inversions?

   A good answer says what one shift fixes.

   Sample answer

   Each shift moves one bigger number past the key, fixing exactly one out-of-order pair. So the shifts equal the inversions, plus about one comparison per key.

6. What is its time and space complexity?
   Sample answer

   $O(n)$ in the best case on sorted input, $O(n^2)$ on average and in the worst case on reversed input. Extra space is $O(1)$.

7. After $k$ steps, how is insertion sort's prefix different from selection sort's?
   Sample answer

   Insertion sort's prefix is sorted but not final, since smaller numbers can still arrive. Selection sort's prefix holds the $k$ smallest values in their final places.

8. Why do real libraries use insertion sort for small arrays instead of merge sort or quick sort?
   Sample answer

   On a few dozen items, its tiny loop and lack of recursion beat the overhead of the $O(n \log n)$ sorts. On nearly sorted data it's close to $O(n)$ anyway.

9. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the inversion count and the $\Theta(n + I)$ formula. I'd keep the card analogy, one insertion on a small array, and "$O(n^2)$ worst, $O(n)$ if nearly sorted, stable, in-place". The picture matters more than the proof.

External resources

• VisuAlgo: Sorting: pick "INS" and step through insertion sort on your own input.
• Toptal: Insertion sort animation: see how fast it is on nearly sorted data.
• GeeksforGeeks: Insertion sort: an article with code in several languages.
• Wikipedia: Insertion sort: analysis, variants and its use inside hybrid sorts.

Videos

• YouTube: insertion sort as a Romanian folk dance: the AlgoRythmics video, a fun way to see the shifts.
• YouTube search: insertion sort explained: pick a short walkthrough.