Insertion Sort Visualizer

Insertion sort is the algorithm you already know. If you have ever picked up a hand of playing cards and slid each new card into place among the ones you were holding, you have executed it — including the part where you stop sliding as soon as you hit a lower card, which is the optimisation that gives the algorithm its linear best case.

It is also the only quadratic sort that survives in production. Every serious library sort — Timsort in Python and Java, introsort in C++ — switches to insertion sort once a partition gets small, because below roughly twenty elements it genuinely beats the O(n log n) algorithms.

What is insertion sort?

Insertion sort builds a sorted region one element at a time. The first element is trivially a sorted list of length one. Each subsequent element — the key — is lifted out, compared backwards against the sorted region, and dropped into the gap where it belongs while everything larger shifts one place right.

The word that matters is *shift*, not swap. A swap is two writes; a shift is one. Bubble sort moves an element three positions left by performing three swaps, or six writes. Insertion sort does it with three shifts and one final placement — four writes. On real data that difference compounds into insertion sort being roughly twice as fast as bubble sort for identical comparison counts.

The second thing that matters is the early break. The inner loop stops the moment it finds an element that is not greater than the key, because everything further left is already known to be smaller. On sorted input that check fails immediately every single time, and the whole algorithm collapses to one comparison per element.

Why it works

The invariant is: before iteration i, the sub-array A[0..i−1] contains the first i elements in sorted order. It is true at the start with i = 1, since a single element is sorted. Each iteration takes A[i], finds its correct position among the first i elements, and shifts the larger ones right to make room — leaving A[0..i] sorted and extending the invariant.

After the final iteration, i equals n, so A[0..n−1] is sorted. That is the whole array, and the proof is complete.

The subtlety worth noticing is that the sorted prefix is sorted but not *final*. Unlike selection sort, where a placed element never moves again, insertion sort's prefix elements shift right repeatedly as new keys arrive. The prefix is correct relative to itself, which is all the invariant claims and all the proof needs.

Step-by-step walkthrough

Take [12, 11, 13, 5, 6] and follow each insertion.

1. The prefix starts as [12]. Key = 11. Compare with 12: larger, so shift 12 right. The gap is now at position 1, and 11 drops in: [11, 12, 13, 5, 6].
2. Key = 13. Compare with 12: not greater, so break immediately. One comparison, no shifts, no writes: [11, 12, 13, 5, 6].
3. Key = 5. Compare with 13, 12 and 11 in turn — all larger, all shift right. 5 lands at the front: [5, 11, 12, 13, 6].
4. Key = 6. Compare with 13, 12, 11 (shift each), then 5, which is not greater, so break. 6 drops into the gap: [5, 6, 11, 12, 13].

Why real library sorts fall back to it

Asymptotic analysis discards constant factors, which is exactly the information that decides small-array performance. Merge sort at n = 10 pays for recursive calls, an auxiliary allocation and merge bookkeeping. Insertion sort at n = 10 executes a tight double loop over contiguous memory with no allocation and no function calls at all.

It also has near-perfect cache behaviour. Each key is compared against elements immediately to its left, which are already in the same cache line. Quick sort and merge sort both stride across memory in ways that miss the cache far more often. On modern hardware a cache miss costs roughly as much as a hundred comparisons, so an algorithm that never misses can afford to do many more of them.

This is why Timsort — Python's sorted() and Java's Arrays.sort() for objects — is built on runs sorted by binary insertion sort, and why introsort in the C++ standard library stops recursing below a threshold and finishes with a single insertion sort pass over the whole nearly-sorted array. Insertion sort is not a teaching relic; it is a component of the fastest sorts in the world.

How the animation above works

Set the arrangement to nearly sorted and press play. Insertion sort will finish almost instantly, and the comparison counter will land close to n rather than n². Then switch to reversed and watch the same algorithm crawl — every key must travel the entire length of the sorted prefix, giving the full n(n−1)/2 comparisons.

That single experiment is the most valuable thing on this page. The best case and worst case of an adaptive algorithm are not abstractions; they are two visibly different behaviours from identical code, and the input alone decides which one you get.

In the bar display, coral marks the shift writes as the gap opens, and amber marks the backwards comparisons. Notice that on a reversed array almost every comparison produces a shift, while on a nearly-sorted array almost none do.

Time complexity

Best case O(n). On an already-sorted array, each key is compared once with its left neighbour, the comparison fails, and the inner loop breaks. That is n−1 comparisons and zero shifts across the whole run — genuinely linear, and faster than any O(n log n) sort on that input.

Worst case O(n²). On a reversed array, key i must be compared against and shift past all i preceding elements, summing to n(n−1)/2 comparisons and the same number of shifts.

Average case O(n²). On random input each key travels about halfway through the sorted prefix, giving roughly n²/4 comparisons. The constant factor is small, which is why it wins at small n despite the quadratic curve.

More precisely, insertion sort runs in O(n + d) time where d is the number of inversions in the input. This is the cleanest statement of adaptivity available: the algorithm's cost is proportional to how far the data actually is from sorted, and for nearly-sorted data d is small.

Space and stability

O(1) auxiliary space — one variable holding the key, plus loop counters. Everything happens in the original array.

Stable, provided the inner loop uses a strict comparison (A[j] > key, not >=). When the loop meets an element equal to the key it stops, leaving the key to the right of its equal — which is exactly where it started. Change that to >= and the algorithm still sorts correctly but shifts equal elements unnecessarily and loses stability.

It is also online: it can sort a stream, inserting each new element as it arrives without needing to see the rest. Almost no other sorting algorithm has this property, and it makes insertion sort the natural choice for maintaining a small sorted buffer that receives values one at a time.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Insertion Sort in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Insertion sort. Shifts rather than swaps, so it performs roughly half the
 * writes of bubble sort for the same number of comparisons.
 */
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;

    // Strict > keeps the sort stable: we stop at the first equal element.
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = key;
  }

  return arr;
}

console.log(insertionSort([12, 11, 13, 5, 6])); // [5, 6, 11, 12, 13]

Advantages and disadvantages

Real-world applications

• The small-array base case inside Timsort and introsort — the reason Python's sorted() and C++'s std::sort are as fast as they are on real data.
• Maintaining a small sorted buffer that receives values one at a time, such as the k nearest results in a search or a leaderboard of fixed size.
• Sorting data known to be nearly ordered — log entries arriving slightly out of sequence, or a list re-sorted after a handful of edits.
• Embedded and real-time systems where code size matters and n is known to be small.
• The final polishing pass in hybrid schemes: run a coarse partitioning algorithm, then a single insertion sort over the almost-sorted result.

Interview questions

The questions that actually get asked about Insertion Sort, with the answers an interviewer is listening for.

1. Q1. Why do production sorting libraries fall back to insertion sort for small arrays?

   Because asymptotic analysis hides constant factors, and at small n those factors decide everything. Insertion sort has no recursion, no allocation and near-perfect cache locality, while merge sort pays for a scratch buffer and quick sort for partitioning overhead. Below roughly twenty elements the tight double loop simply wins, so Timsort and introsort both switch to it.

2. Q2. Explain why insertion sort is O(n) in the best case.

   On sorted input the inner while loop's condition arr[j] > key fails on the first test for every key, because each new element is already at least as large as its left neighbour. That is one comparison per element and zero shifts, giving n−1 comparisons in total — linear.

3. Q3. What is binary insertion sort, and does it improve the complexity?

   It replaces the linear backwards scan with a binary search for the insertion point, reducing comparisons from O(n²) to O(n log n). The overall time complexity stays O(n²), because the elements still have to be physically shifted to make room. It is worth doing only when comparisons are much more expensive than moves — long strings, or comparator functions that do real work.

4. Q4. How does insertion sort compare with bubble sort?

   They have identical asymptotics — O(n²) average, O(n) best with the right optimisations — but insertion sort is roughly twice as fast in practice because it shifts (one write) rather than swaps (two writes), and it breaks out of the inner loop as soon as the position is found rather than always scanning to the end.

5. Q5. What makes insertion sort stable, and how easily is that broken?

   The inner loop uses a strict > comparison, so it stops at the first element equal to the key, leaving the key to the right of its equal — its original relative position. Changing the comparison to >= breaks stability immediately and also does more work, so it is a strictly worse choice.

Common mistakes

• Using >= instead of > in the inner loop, which breaks stability and performs unnecessary shifts.
• Writing the key back with arr[j] = key instead of arr[j + 1] = key — after the loop, j has already moved one step past the insertion point.
• Forgetting the j >= 0 bound check, which reads before the start of the array when the key is smaller than every element seen so far.
• Starting the outer loop at i = 0, which treats the first element as needing insertion into an empty prefix and does nothing useful.
• Swapping instead of shifting: swap(arr[j], arr[j+1]) in a loop produces correct output but doubles the writes, turning insertion sort into bubble sort with extra steps.
• Reading the key inside the inner loop rather than caching it before — once shifting begins, arr[i] no longer holds the original value.

Optimisation tips

• Use binary search to locate the insertion point when comparisons are expensive; keep the linear scan when they are cheap, since it has better locality.
• Add a sentinel: place the minimum element at position 0 first, and the inner loop no longer needs its j >= 0 bound check.
• For linked lists, insertion sort needs no shifting at all — relink the node instead — which changes the write cost profile completely.
• Detect existing runs before sorting. If the data arrives in ascending stretches, sorting each run and merging them is what Timsort does, and it beats a plain insertion sort badly on real data.
• Use it as the base case of a divide-and-conquer sort rather than as the whole algorithm: recurse until partitions fall under about sixteen elements, then run one insertion sort pass over everything.

Summary

Insertion sort grows a sorted prefix by lifting each element out, shifting larger values right, and dropping it into the gap. It is O(n) on sorted input, O(n²) on reversed input, and O(n + d) in general where d is the number of inversions — the cleanest definition of an adaptive sort.

It is stable, in place, online, and cache-friendly, with a small enough constant factor that it beats O(n log n) algorithms below roughly twenty elements. That is not a curiosity: it is why Timsort and introsort both use it internally, making insertion sort a live component of the fastest sorting code in production today.

Frequently asked questions

Related algorithms

• Bubble Sort

  Repeatedly swap adjacent pairs until the largest values have bubbled to the end.

  O(n²)Beginner

• Selection Sort

  Scan for the smallest remaining value and swap it into place — one swap per pass.

  O(n²)Beginner

• Merge Sort

  Split the array down to single elements, then merge sorted halves back together.

  O(n log n)Intermediate