Insertion Sort Complete Guide

Algorithm • medium

Insertion sort keeps a growing sorted prefix and inserts each new value into its correct position.

It is especially strong for tiny datasets or nearly sorted input where each insertion shifts very little.

Many high-performance sort implementations still use insertion sort for small partitions.

Typical Complexity Baseline

Metric	Value
Complexity Note 1	Average/Worst `O(n^2)`
Best	`O(n)`
Space	`O(1)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Insertion sort pick and place

Take the next element and shift the sorted prefix right until its slot opens up.

Step 1/25Sorted prefix is just [4]. Pick the next element and slide it left until it lands in place.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Insertion Sort - Algorithms in 60 Seconds

Channel: OpenAMind

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Sorted prefix

What it is Left side is maintained in sorted order.

Why it matters Sorted prefix is a required building block for understanding how Insertion Sort stays correct and performant on large inputs.

Current key

What it is Value selected for insertion into sorted prefix.

Why it matters Current key is a required building block for understanding how Insertion Sort stays correct and performant on large inputs.

Shift loop

What it is Moves larger values right to make room.

Why it matters Shift loop is a required building block for understanding how Insertion Sort stays correct and performant on large inputs.

Insert position

What it is Final slot where the key is placed.

Why it matters Insert position is a required building block for understanding how Insertion Sort stays correct and performant on large inputs.

Outer pointer

What it is Advances to next unsorted value.

Why it matters Outer pointer is a required building block for understanding how Insertion Sort stays correct and performant on large inputs.

Insertion position

What it is Index where current value belongs in sorted prefix.

Why it matters Index where current value belongs in sorted prefix. In Insertion Sort, this definition helps you reason about correctness and complexity when inputs scale.

Stable sort

What it is Equal values preserve original relative order.

Why it matters Equal values preserve original relative order. In Insertion Sort, this definition helps you reason about correctness and complexity when inputs scale.

Adaptive behavior

What it is Runs faster when input is partially sorted.

Why it matters Runs faster when input is partially sorted. In Insertion Sort, this definition helps you reason about correctness and complexity when inputs scale.

In-place sort

What it is Sorts by mutating original array with O(1) extra space.

Why it matters Sorts by mutating original array with O(1) extra space. In Insertion Sort, this definition helps you reason about correctness and complexity when inputs scale.

Shift

What it is Move an element one slot right to open insertion space.

Why it matters Move an element one slot right to open insertion space. In Insertion Sort, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/25

Sorted prefix is just [4]. Pick the next element and slide it left until it lands in place.

Step 2/25

Pick arr[1]=7. Compare with arr[0]=4.

Step 3/25

7 dropped into slot 1. Sorted prefix is now [4, 7].

Step 4/25

Pick arr[2]=2. Compare with arr[1]=7.

Step 5/25

2 < 7 → shift right. Now compare with arr[0]=4.

Step 6/25

2 reached the start → it's the new minimum.

Step 7/25

2 dropped into slot 0. Sorted prefix is now [2, 4, 7].

Step 8/25

Pick arr[3]=5. Compare with arr[2]=7.

Step 9/25

5 < 7 → shift right. Now compare with arr[1]=4.

Step 10/25

5 dropped into slot 2. Sorted prefix is now [2, 4, 5, 7].

Step 11/25

Pick arr[4]=1. Compare with arr[3]=7.

Step 12/25

1 < 7 → shift right. Now compare with arr[2]=5.

Step 13/25

1 < 5 → shift right. Now compare with arr[1]=4.

Step 14/25

1 < 4 → shift right. Now compare with arr[0]=2.

Step 15/25

1 reached the start → it's the new minimum.

Step 16/25

1 dropped into slot 0. Sorted prefix is now [1, 2, 4, 5, 7].

Step 17/25

Pick arr[5]=6. Compare with arr[4]=7.

Step 18/25

6 < 7 → shift right. Now compare with arr[3]=5.

Step 19/25

6 dropped into slot 4. Sorted prefix is now [1, 2, 4, 5, 6, 7].

Step 20/25

Pick arr[6]=3. Compare with arr[5]=7.

Step 21/25

3 < 7 → shift right. Now compare with arr[4]=6.

Step 22/25

3 < 6 → shift right. Now compare with arr[3]=5.

Step 23/25

3 < 5 → shift right. Now compare with arr[2]=4.

Step 24/25

3 < 4 → shift right. Now compare with arr[1]=2.

Step 25/25

3 dropped into slot 2. Sorted prefix is now [1, 2, 3, 4, 5, 6, 7].

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Bubble Sort

Choose this when Choose insertion sort for fewer writes on nearly sorted input.

Tradeoff Both are O(n^2) worst-case on random/reversed arrays.

vs. Merge Sort

Choose this when Choose insertion sort for small arrays where low overhead matters.

Tradeoff Merge sort scales better for large input sizes.

vs. Quick Sort

Choose this when Choose insertion sort for tiny partitions in hybrid approaches.

Tradeoff Quick sort dominates on larger random datasets.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Language runtime libraries

Standard library sort implementations often switch to insertion sort on very small partitions.

Takeaway Simple algorithms can be optimal in specific ranges.

Spreadsheet software

Small row groups and incremental updates benefit from insertion-style behavior.

Takeaway Nearly sorted data changes are often cheaper than full resorting.

Embedded systems

Firmware code paths with tiny arrays choose insertion sort for minimal implementation overhead.

Takeaway Operational constraints can favor simplicity and predictability.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Take each value, shift larger values right, and insert into the gap.

Complexity: Average/Worst O(n^2), Best O(n), Space O(1)

Insertion sort with shifting

Language

function insertionSort(values: number[]): number[] {
  const sortedValues = [...values]
  for (let insertionIndex = 1; insertionIndex < sortedValues.length; insertionIndex += 1) {
    const currentValue = sortedValues[insertionIndex]
    let compareIndex = insertionIndex - 1

    while (compareIndex >= 0 && sortedValues[compareIndex] > currentValue) {
      sortedValues[compareIndex + 1] = sortedValues[compareIndex]
      compareIndex -= 1
    }

    sortedValues[compareIndex + 1] = currentValue
  }

  return sortedValues
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Overwriting key value before insertion.
Off-by-one errors while shifting values.
Using insertion sort on large random datasets.
Not handling already sorted input as a fast path mentally.
Forgetting stability expectations when customizing comparisons.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Think of the left side as always sorted, and insert the next value into that region.
Insertion sort is very efficient on nearly sorted input because shifts stay small.
Store current value before shifting to avoid overwriting data.
Use insertion sort for tiny partitions in hybrid production sorts.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Simple in-place implementation with no extra array allocation.
Excellent practical behavior on near-sorted arrays.
Common fallback in hybrid sorting strategies.

LeetCode-specific tips (pattern-identification signals)

Identification signal: data is nearly sorted or small; each new item is inserted into prior sorted prefix.
Identification signal: prompt hints at online insertion behavior rather than full divide-and-conquer split.
If stable in-place simple sorting is acceptable for small n, insertion sort is often right.
For Insertion Sort questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Relative Sort Array	Easy	`O(n log n)`
2	Sort an Array	Medium	`O(n^2)` insertion approach
3	Insertion Sort List	Medium	`O(n^2)`
4	Sort Colors	Medium	`O(n)` optimal, `O(n^2)` insertion naive
5	Largest Number	Medium	`O(n log n)`
6	Wiggle Sort II	Medium	`O(n log n)`
7	Sort List	Medium	`O(n log n)` target
8	Count of Smaller Numbers After Self	Hard	`O(n log n)`
9	Reverse Pairs	Hard	`O(n log n)`
10	Median of Two Sorted Arrays	Hard	`O(log(min(m,n)))`