# 3.3 Insertion Sort

> Grow a sorted part on the left by inserting each new item into its correct place, like sorting cards in your hand. Fast on nearly sorted data.

Chapter: Simple Sorting & Searching · ~40 min · easy
URL: https://dsa.fetehadin.com/learn/insertion-sort

## Mental model

You're dealt cards one at a time. Your hand is always sorted: each new card slides left past the bigger ones until it finds its spot. You never re-sort the whole hand. That's insertion sort.

### The idea

- The part `a[0..i-1]` is always **sorted**.
- Take `key = a[i]`.
- Walk left from `i - 1`, **shifting** every item bigger than `key` one place right.
- When you hit an item ≤ key (or the start), drop `key` into the gap.

### Why it's adaptive

If the array is already sorted, every key is ≥ its left neighbour, so the while loop stops at once: **n − 1 comparisons, O(n)**. If it's reversed, every key travels all the way to the front: **n(n−1)/2**, O(n²). The less "out of order" the data, the faster it runs.

### Shift, don't swap

Each step of the while loop is **one assignment** (`a[j+1] = a[j]`), not a three-assignment swap. That's why insertion sort usually beats bubble sort in practice, even though both are O(n²).

## C++ code: insertion-sort.cpp

```cpp
#include <iostream>
using namespace std;

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {   // shift bigger items right
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;                  // drop key into the gap
    }
}

int main() {
    int a[] = {29, 10, 14, 37, 13, 5};
    int n = sizeof(a) / sizeof(a[0]);
    insertionSort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "\n";
}
```

Expected output:

```text
5 10 13 14 29 37
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case (already sorted) | O(n): n − 1 comparisons, 0 shifts |
| Average case | O(n²) |
| Worst case (reversed) | O(n²): n(n−1)/2 comparisons and shifts |

Space: O(1)
Stable: yes
In-place: yes

Insertion sort is **adaptive** (faster on nearly sorted input) and **online** (it can sort items as they arrive). Real libraries use it for small sub-arrays.

## Videos

- [Insertion sort algorithm](https://youtu.be/i-SKeOcBwko) (mycodeschool): Builds the "shift right, then drop the key" loop carefully and analyses the cases.
- [Insertion sort in 2 minutes](https://youtu.be/JU767SDMDvA) (Michael Sambol): Two-minute animation to lock in the picture.

## Exam lens

Likely questions:

- Trace insertion sort on `12, 11, 13, 5, 6`, showing the array after each insertion.
- What are the best and worst case inputs and complexities of insertion sort?
- Why does insertion sort perform well on nearly sorted data?
- Compare insertion sort with selection sort.

Common mistakes:

- Writing `a[j] >= key` in the while loop. That breaks stability.
- Forgetting `j >= 0` in the loop condition, which reads `a[-1]`.
- Putting `a[j + 1] = key` inside the while loop. It goes **after** the loop.
- Starting the outer loop at `i = 0`. Item 0 alone is already "sorted", so start at 1.

## Quick check

1. Insertion sort on `2, 3, 4, 5, 1`: how many shifts happen in total?
   A. 1
   B. 4
   C. 5
   D. 10
   Answer: B. Only the last key (1) moves, shifting 2, 3, 4 and 5 one place right.

2. Best case of insertion sort?
   A. O(1)
   B. O(n)
   C. O(n log n)
   D. O(n²)
   Answer: B. Each key is compared once with its left neighbour and stays put.

3. What does the inner while loop do?
   A. Finds the minimum
   B. Swaps neighbours until sorted
   C. Shifts larger items right to open a gap for key
   D. Splits the array
   Answer: C. Shifting (one assignment each) is cheaper than swapping (three assignments).

4. Which sort is best for an array that is already sorted except for 2 items?
   A. Selection sort
   B. Insertion sort
   C. All are the same
   D. None
   Answer: B. It is adaptive, so the work is close to O(n). Selection sort would still do n²/2 comparisons.

## Practice

**Trace by hand.** Trace insertion sort on `12, 11, 13, 5, 6`. Write the array after each value of i.

Solution:

- i = 1 (key 11): `11 12 13 5 6`
- i = 2 (key 13): `11 12 13 5 6` (no shift)
- i = 3 (key 5): `5 11 12 13 6` (3 shifts)
- i = 4 (key 6): `5 6 11 12 13` (3 shifts)


**Implement it.** Write `insertionSortDesc` (descending order), then a version that sorts an array of `string` names alphabetically.

Hint: Only the comparison changes. `string` supports `<` and `>` out of the box.

**Problems:**

- [Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/) (medium). Hint: Same idea on a linked list. Use a dummy head for the sorted list and insert each node after the right predecessor (revisit after Chapter 4).
- [Sort an Array](https://leetcode.com/problems/sort-an-array/) (medium). Hint: Insertion sort will time out on the large tests, which shows why O(n²) matters.
- [Insertion Sort - Part 1 (HackerRank)](https://www.hackerrank.com/challenges/insertionsort1/problem) (easy). Hint: Print the array after every shift. A great tracing exercise.

## Mastery checklist

- [ ] I can trace insertion sort and show every shift.
- [ ] I can write it from memory with the correct while condition.
- [ ] I can name the best/worst inputs and their complexities.
- [ ] I can explain why it is stable and adaptive.