Sorting · Beginner

Insertion Sort

Slide each new element into its place in the sorted prefix — the quadratic sort that production code actually uses.

AverageO(n²)StableYesIn-placeYesComparisonYes

Hands on Interactive visualization

Speed

Step 0 / 0

Comparisons

Swaps

Reads

Writes

Elapsed

0.0s

Frames

Depth

0 / 0

Aux memory

0 B

Implementation Code

export function insertionSort(a: number[]): number[] {
  for (let i = 1; i < a.length; i++) {
    const key = a[i]; // element to place into the sorted prefix
    let j = i - 1;
    // Shift larger elements one slot right (strict > keeps stability).
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key; // drop the key into the gap
  }
  return a;
}

Big-O Complexity

Best

O(n)

Average

O(n²)

Worst

O(n²)

Space

O(1)

Runtime is O(n + d) where d is the number of inversions — near-linear on nearly-sorted data.

StableYesIn-placeYesComparisonYesRecursiveNoAdaptiveYesOnlineYes

In production When to use

Backend / stdlib internals

Nearly every production hybrid sort — TimSort (Python, Java objects, V8), pdqsort (Go, Rust unstable), introsort (C++) — switches to insertion sort for small partitions, typically under 16–32 elements.

Game dev

Per-frame lists (sprites by depth, entities by distance) barely change between frames. Insertion sort on the previous frame's order runs in near-linear time.

Streaming / Online

It is a true online algorithm: elements can arrive one at a time and each is placed as it lands, keeping the collection sorted at every moment.

Embedded

O(1) memory, no recursion, and a tiny code footprint make it the default for sorting small buffers on allocator-free firmware.

Database

Insertion into small sorted runs and node-level ordering in B-tree pages amounts to insertion sort: shift the tail, drop in the new key.

Frontend

Maintaining a small sorted list under interactive edits (adding a row to a sorted table) is exactly one insertion pass — no need to re-sort the whole array.

Trade-offs Strengths & weaknesses

Adaptive: cost scales with the number of inversions, so nearly-sorted input is near-linear.
Stable — equal keys never cross each other.
Online: can sort a stream as elements arrive.
In-place, O(1) memory, tiny code size.
Very low constant factors: the fastest sort in practice below roughly 20–30 elements.
Shift-based inner loop does one write per moved element, unlike bubble sort's swap pairs.

O(n²) average and worst case — unusable as a general sort at scale.
Reverse-sorted input is its pathological case: maximal shifts every step.
Each insertion is sequential; the algorithm offers little parallelism.
Shifting large records is expensive — indirection (sorting pointers/indices) is needed for wide payloads.

Intuition Mental model

Sorting a hand of playing cards

Exactly how most people sort cards dealt one at a time: everything in your hand stays sorted, and each new card slides in where it belongs.

Your left hand holds the cards received so far, already in order.
Pick up the next card (the key) and hold it — its old slot is now free.
Scan right-to-left through your hand, sliding larger cards one slot over.
Drop the new card into the gap that opens where it fits.
The hand is sorted after every single card — that is the online property.

Prep Interview questions

Why do industrial-strength sorts like TimSort and introsort switch to insertion sort for small subarrays?

Below a few dozen elements, insertion sort's tiny constants, cache-resident working set, and lack of recursion overhead beat the asymptotic advantage of divide-and-conquer.

Express insertion sort's runtime in terms of inversions.

Each inner-loop shift removes exactly one inversion, so total time is O(n + d) where d is the inversion count. Sorted input has d = 0; reverse-sorted has d = n(n-1)/2.

Why shift elements instead of swapping like bubble sort?

A swap is three writes; a shift is one. Holding the key in a register and writing it once at the end cuts memory traffic roughly threefold in the inner loop.

Could you speed up finding the insertion point with binary search? Does it change the complexity?

Binary insertion sort cuts comparisons to O(n log n), but shifting elements is still O(n²) writes in the worst case — the complexity class does not change.

What makes insertion sort 'online' and why does selection sort fail that test?

Insertion sort only needs the elements seen so far, kept sorted. Selection sort must scan the entire remaining input to find the minimum, so it needs all data up front.

Watch out Common bugs

Starting the outer loop at index 0

The prefix of length 1 is already sorted; starting at 0 wastes a pass at best, and in while-loop formulations can underflow the inner index.

Using >= instead of > when shifting

Shifting while a[j] >= key moves equal elements past each other, silently breaking stability — invisible with ints, a real bug when sorting records by key.

Writing the key back at the wrong index

After the while loop, the key belongs at j + 1 (or j in the 'j starts at i' formulation). Off-by-one here overwrites a neighbor and drops an element.

Unsigned index underflow in the inner loop

In Rust/C with unsigned indices, the condition j >= 0 is always true. Compare j > 0 and index a[j - 1], or the loop wraps around and panics.

One screen Cheat sheet

Grow a sorted prefix; shift bigger elements right and drop each new key into the gap.

Best O(n) · Avg O(n²) · Worst O(n²) · Space O(1)

Stable, in-place, adaptive, online — the full house of nice properties.
Runtime is O(n + inversions): great on nearly-sorted data.
The small-array workhorse inside TimSort, pdqsort, and introsort.
Shift (one write) beats swap (three writes) in the inner loop.
Strict > in the shift condition is what preserves stability.
Binary search for the position helps comparisons, not the O(n²) shifts.

Pick whenSmall arrays (< ~30), nearly-sorted data, streaming input, or the base case of a hybrid sort.

Avoid whenLarge random or reverse-ordered datasets — inversions, and therefore cost, explode quadratically.

Implementation Code

export function insertionSort(a: number[]): number[] {
  for (let i = 1; i < a.length; i++) {
    const key = a[i]; // element to place into the sorted prefix
    let j = i - 1;
    // Shift larger elements one slot right (strict > keeps stability).
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key; // drop the key into the gap
  }
  return a;
}

In production When to use

Backend / stdlib internals

Game dev

Per-frame lists (sprites by depth, entities by distance) barely change between frames. Insertion sort on the previous frame's order runs in near-linear time.

Streaming / Online

It is a true online algorithm: elements can arrive one at a time and each is placed as it lands, keeping the collection sorted at every moment.

Embedded

O(1) memory, no recursion, and a tiny code footprint make it the default for sorting small buffers on allocator-free firmware.

Database

Insertion into small sorted runs and node-level ordering in B-tree pages amounts to insertion sort: shift the tail, drop in the new key.

Frontend

Maintaining a small sorted list under interactive edits (adding a row to a sorted table) is exactly one insertion pass — no need to re-sort the whole array.

Trade-offs Strengths & weaknesses

Adaptive: cost scales with the number of inversions, so nearly-sorted input is near-linear.
Stable — equal keys never cross each other.
Online: can sort a stream as elements arrive.
In-place, O(1) memory, tiny code size.
Very low constant factors: the fastest sort in practice below roughly 20–30 elements.
Shift-based inner loop does one write per moved element, unlike bubble sort's swap pairs.

O(n²) average and worst case — unusable as a general sort at scale.
Reverse-sorted input is its pathological case: maximal shifts every step.
Each insertion is sequential; the algorithm offers little parallelism.
Shifting large records is expensive — indirection (sorting pointers/indices) is needed for wide payloads.

Intuition Mental model

Sorting a hand of playing cards

Exactly how most people sort cards dealt one at a time: everything in your hand stays sorted, and each new card slides in where it belongs.

Your left hand holds the cards received so far, already in order.
Pick up the next card (the key) and hold it — its old slot is now free.
Scan right-to-left through your hand, sliding larger cards one slot over.
Drop the new card into the gap that opens where it fits.
The hand is sorted after every single card — that is the online property.

Prep Interview questions

Why do industrial-strength sorts like TimSort and introsort switch to insertion sort for small subarrays?

Below a few dozen elements, insertion sort's tiny constants, cache-resident working set, and lack of recursion overhead beat the asymptotic advantage of divide-and-conquer.

Express insertion sort's runtime in terms of inversions.

Each inner-loop shift removes exactly one inversion, so total time is O(n + d) where d is the inversion count. Sorted input has d = 0; reverse-sorted has d = n(n-1)/2.

Why shift elements instead of swapping like bubble sort?

A swap is three writes; a shift is one. Holding the key in a register and writing it once at the end cuts memory traffic roughly threefold in the inner loop.

Could you speed up finding the insertion point with binary search? Does it change the complexity?

Binary insertion sort cuts comparisons to O(n log n), but shifting elements is still O(n²) writes in the worst case — the complexity class does not change.

What makes insertion sort 'online' and why does selection sort fail that test?

Insertion sort only needs the elements seen so far, kept sorted. Selection sort must scan the entire remaining input to find the minimum, so it needs all data up front.

Watch out Common bugs

Starting the outer loop at index 0

The prefix of length 1 is already sorted; starting at 0 wastes a pass at best, and in while-loop formulations can underflow the inner index.

Using >= instead of > when shifting

Shifting while a[j] >= key moves equal elements past each other, silently breaking stability — invisible with ints, a real bug when sorting records by key.

Writing the key back at the wrong index

After the while loop, the key belongs at j + 1 (or j in the 'j starts at i' formulation). Off-by-one here overwrites a neighbor and drops an element.

Unsigned index underflow in the inner loop

In Rust/C with unsigned indices, the condition j >= 0 is always true. Compare j > 0 and index a[j - 1], or the loop wraps around and panics.

One screen Cheat sheet

Grow a sorted prefix; shift bigger elements right and drop each new key into the gap.

Best O(n) · Avg O(n²) · Worst O(n²) · Space O(1)

Stable, in-place, adaptive, online — the full house of nice properties.
Runtime is O(n + inversions): great on nearly-sorted data.
The small-array workhorse inside TimSort, pdqsort, and introsort.
Shift (one write) beats swap (three writes) in the inner loop.
Strict > in the shift condition is what preserves stability.
Binary search for the position helps comparisons, not the O(n²) shifts.

Pick whenSmall arrays (< ~30), nearly-sorted data, streaming input, or the base case of a hybrid sort.

Avoid whenLarge random or reverse-ordered datasets — inversions, and therefore cost, explode quadratically.