Insertion Sort Complete Guide

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Related Sorting Guides

Bubble, merge, and quick sort are tightly related. Compare them side-by-side to understand tradeoffs in runtime, memory, and stability.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

How It Compares

Real-World Stories and Company Examples

Insertion sort with shifting

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
}

Common Problems and Failure Modes

• 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.

Tips and Tricks

• 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.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

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 (including 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.