---
title: "Insertion Sort"
description: "Build sorted prefix one element at a time"
source: https://vizlearn.app/algorithms/sorting/insertion-sort
---

# Insertion Sort

Insertion sort is a comparison-based sorting algorithm that grows a sorted prefix one element at a time: each pass lifts the next value out of the array, shifts every larger element in the prefix one slot right, and drops the value into its correct place. It is stable, in-place, O(n²) worst case, and O(n) when the input is already sorted.

You already know this algorithm if you have ever played cards. Pick up your hand one card at a time, slide each new card leftward past everything bigger, and tuck it where it fits. Nobody taught you that; it is just the obvious way to keep a hand ordered. Insertion sort is that instinct, written down.

## How Insertion Sort Works

One outer loop, one backward inner loop. The outer loop runs `i` from 1 to n − 1; positions `0..i − 1` are the sorted hand, and `arr[i]` is the new card. Lift it into a variable: `key = arr[i]`. The slot is now logically empty.

The inner loop walks `j` from `i − 1` down toward 0, and as long as `arr[j] > key`, it shifts `arr[j]` one slot right (`arr[j + 1] = arr[j]`) and decrements `j`. The moment it meets a value less than or equal to the key — or falls off the left edge — it stops, and the key drops into `arr[j + 1]`.

The invariant: at the top of every outer pass, `arr[0..i − 1]` is sorted. Each pass preserves it by construction, so when `i` runs off the end, the whole array is the hand.

## Insertion Sort Step by Step

The default input is `[38, 12, 56, 7, 41, 23, 19]`.

Pass 1 (`i = 1`): lift `key = 12`. The hand is `[38]`. Compare: 38 > 12, so 38 shifts right and `j` falls off the edge to −1. The key drops at index 0: `[12, 38, 56, 7, 41, 23, 19]`.

Pass 2 (`i = 2`): lift `key = 56`. Compare against 38 — already smaller than the key, so the loop exits before shifting anything. 56 drops right back where it was. One comparison, zero movement: the cheap case that makes insertion sort fast on friendly input.

Pass 3 (`i = 3`): lift `key = 7`. Now the expensive case — 56, 38, and 12 each shift right in turn, `j` hits −1, and 7 lands at index 0: `[7, 12, 38, 56, 41, 23, 19]`.

The remaining passes repeat the pattern. Pass 4 shifts only 56 and places 41 → `[7, 12, 38, 41, 56, 23, 19]`. Pass 5 shifts 56, 41, 38 and places 23 at index 2 → `[7, 12, 23, 38, 41, 56, 19]`. Pass 6 shifts 56, 41, 38, 23 and places 19 at index 2 → `[7, 12, 19, 23, 38, 41, 56]`. Sorted.

In the animation, the cell at `i` physically lifts out of the row and floats above it as the key while `j` walks left; each shifted cell slides rightward into the gap, and the floating key drops into `j + 1` when the scan stops. The hole moving left is the algorithm.

## Time and Space Complexity

| Case | Time |
|---|---|
| Best (already sorted) | O(n) |
| Average | O(n²) |
| Worst (reverse sorted) | O(n²) |

Space is O(1) — in place. The animated version is the textbook shift-based form (one lifted key, repeated `arr[j + 1] = arr[j]`), not the swap-based variant.

The line that earns the best case is the loop guard: `while j >= 0 and arr[j] > key`. On sorted input it fails on the first value comparison of each pass. More generally, each input inversion causes one shift, so the running time is Θ(n + I), where I is the number of inversions. A low inversion count makes insertion sort cheap; O(n) requires I = O(n). "Nearly sorted" by itself does not give a precise bound. This adaptivity makes insertion sort useful for short runs with little disorder.

## Edge Cases

- **Empty or one-element array** — the outer loop runs zero times.
- **Already sorted input** — every inner loop exits on its first test: n − 1 comparisons total, O(n).
- **All equal values** — `arr[j] > key` is never true, so no shifts ever fire; also O(n).
- **Duplicates** — insertion sort is **stable**: the strict `>` guard stops the scan at an equal value rather than shifting past it, so equal elements keep their original order.

## Common Mistakes

- **Using `>=` instead of `>` in the guard.** The sort still works, but equal values get shifted past each other and stability is gone.
- **Placing the key at `arr[j]` instead of `arr[j + 1]`.** After the loop, `arr[j]` is the element that *passed* the test (or `j` is −1). The empty slot is one to its right.
- **Overwriting before lifting.** Skip `key = arr[i]` and the very first shift destroys the value you were inserting.
- **Shifting the wrong direction.** The body is `arr[j + 1] = arr[j]` — values move right to open the gap. Writing `arr[j] = arr[j - 1]` moves the gap away from where the key must land.