Insertion Sort

in reviewThis lesson is complete and being validated before release - details may still change.

Insertion sort

Loading interactive demo…

Insertion sort slides each new element into place among the ones before it - like sorting cards in your hand. Take the tour, or press and explore. Legend:

The panel beside the stage is the real InsertionSort class from the published library executing in your browser, with the current line highlighted.

The key - the element currently being inserted (always the brightest bar). While larger elements shift right, the key lives in the key variable - its bar turns translucent and glides left to its slot.
A comparison in the while-loop: a sorted-prefix element checked against the key - shifted right if larger; the comparison that comes up smaller-or-equal ends the pass (same color, no shift). The bracket above points at the two elements being compared.
The sorted prefix.
A just-inserted key.

The prefix left of the key is always sorted - that invariant is the whole proof: when the loop ends, the prefix is the array.

Drag the bars to rearrange the array yourself, then press - a nearly-sorted arrangement needs far fewer shifts than a reversed one.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

sort copies the input ([...input]) and never mutates the caller's array - a contract stated by the readonly parameter type.
The loop condition j >= 0 && a[j] > key does two jobs in order: stop at the array's left edge, then stop at the first element not larger than the key. Swapping the checks would read past the array.
Using > rather than >= makes the sort stable: equal elements keep their original order - invisible with plain numbers, a real bug once elements carry more data than their sort key.
The tracer?.emit(...) calls are the library's instrumentation seam: consumers who don't pass a Tracer pay nothing; this widget passes a recorder and replays the events as the visualization.

Insertion sort is how people order things by hand - pick up the next card, slide it left until it fits. It was among the first methods discussed when electronic computers made sorting a programming problem in the 1940s, and it never left: its simplicity and speed on small or nearly-sorted inputs keep it inside the industrial-strength sorts shipped today.

1946John Mauchly - Moore School Lectures include the first published discussion of sorting for electronic computers, insertion among the methods.source
1973Donald Knuth - The Art of Computer Programming Vol. 3 gives the definitive analysis of sorting by straight insertion.source
2002Tim Peters - Timsort ships in CPython, running binary insertion sort on short runs before merging them.source

Used today

Timsort's small runs - Python's sorted() and Java's object sort hand short runs to insertion sort before merging.
Small-array cutoffs - Production quicksorts (introsort, pdqsort) switch to insertion sort below a few dozen elements.
Nearly-sorted data - Adaptive: close-to-ordered input finishes in near-linear time, ideal for maintaining sorted lists online.

Did you know

Before inventing quicksort, Tony Hoare's first idea for sorting Russian words in Moscow was insertion sort. Only after realizing it would be too slow did he go looking for something faster.source
Asked by Google's CEO Eric Schmidt in 2007 how he would sort a million integers, presidential candidate Barack Obama answered: 'I think the bubble sort would be the wrong way to go.'source
Library sort, also called gapped insertion sort, is named after a librarian who leaves empty space after every letter on the shelf so a new book only pushes a few neighbours aside instead of the whole row.source
In 1981 Ronald Baecker's 30-minute film 'Sorting Out Sorting' animated nine sorting algorithms, opening with linear and binary insertion sort - one of the first algorithm animations ever made.source
Timsort, the Python sort that hands short runs to insertion sort, hid a bug for 13 years: formal verification found it in 2015, and the smallest Java input that triggers it has 67,108,864 elements.source

n16

comparisons: 0
insertions: 0

insertion-sort.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Insertion sort: grow a sorted prefix one element at a time by * inserting each new element into its correct position. * * Time: O(n²) worst case, O(n) when nearly sorted. Space: O(1) extra. */export class InsertionSort implements SortAlgorithm {  readonly name = "insertion-sort";  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    for (let i = 1; i < a.length; i++) {    for (let position = 1; position < array.length; position++) {      const key = a[i]!;      const key = array[position]!;      // ▸ pick the next unsorted element - call it the key      this.tracer?.emit("select-key", { i, key, array: [...a] });      this.tracer?.emit("select-key", { position, key, array: [...array] });      let j = i - 1;      let scanIndex = position - 1;      while (j >= 0 && a[j]! > key) {      while (scanIndex >= 0 && array[scanIndex]! > key) {        // ▸ the neighbor on the left is bigger - shift it one slot right        this.tracer?.emit("compare-shift", { i, j, key, array: [...a] });        this.tracer?.emit("compare-shift", { position, scanIndex, key, array: [...array] });        a[j + 1] = a[j]!;        array[scanIndex + 1] = array[scanIndex]!;        j--;        scanIndex--;      }      // ▸ the neighbor is not bigger - the key's slot is found      if (j >= 0) this.tracer?.emit("compare-stop", { i, j, key, array: [...a] });      if (scanIndex >= 0) this.tracer?.emit("compare-stop", { position, scanIndex, key, array: [...array] });      a[j + 1] = key;      array[scanIndex + 1] = key;      // ▸ drop the key into the open slot      this.tracer?.emit("insert", { i, at: j + 1, key, array: [...a] });      this.tracer?.emit("insert", { position, at: scanIndex + 1, key, array: [...array] });    }    return a;    return array;  }}

The array before sorting. The first element alone is a sorted prefix.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Insertion sort: grow a sorted prefix one element at a time by * inserting each new element into its correct position. * * Time: O(n²) worst case, O(n) when nearly sorted. Space: O(1) extra. */export class InsertionSort implements SortAlgorithm { readonly name = "insertion-sort"; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; for (let i = 1; i < a.length; i++) { for (let position = 1; position < array.length; position++) { const key = a[i]!; const key = array[position]!; // ▸ pick the next unsorted element - call it the key this.tracer?.emit("select-key", { i, key, array: [...a] }); this.tracer?.emit("select-key", { position, key, array: [...array] }); let j = i - 1; let scanIndex = position - 1; while (j >= 0 && a[j]! > key) { while (scanIndex >= 0 && array[scanIndex]! > key) { // ▸ the neighbor on the left is bigger - shift it one slot right this.tracer?.emit("compare-shift", { i, j, key, array: [...a] }); this.tracer?.emit("compare-shift", { position, scanIndex, key, array: [...array] }); a[j + 1] = a[j]!; array[scanIndex + 1] = array[scanIndex]!; j--; scanIndex--; } // ▸ the neighbor is not bigger - the key's slot is found if (j >= 0) this.tracer?.emit("compare-stop", { i, j, key, array: [...a] }); if (scanIndex >= 0) this.tracer?.emit("compare-stop", { position, scanIndex, key, array: [...array] }); a[j + 1] = key; array[scanIndex + 1] = key; // ▸ drop the key into the open slot this.tracer?.emit("insert", { i, at: j + 1, key, array: [...a] }); this.tracer?.emit("insert", { position, at: scanIndex + 1, key, array: [...array] }); } return a; return array; }}