# Insertion Sort
**URL:** https://thecodex.expert/coding/algorithms/sorting/insertion-sort/
**Type:** algorithm | **Confidence:** high | **Verified:** 2026-06-01

## CANONICAL DEFINITION
Insertion sort is a comparison-based sorting algorithm that builds the sorted array one element at a time by inserting each unsorted element into its correct position among already-sorted elements — O(n) on nearly-sorted data, Theta(n^2) average, O(1) space.

## COMPLEXITY
- best: O(n)
- average: Theta(n^2)
- worst: Theta(n^2)
- space: O(1)
- stability: stable

## REQUIRES
algorithms/sorting, algorithms/complexity

## ENABLES
algorithms/sorting/heapsort

## SOURCES
- CLRS 4th ed. §2.1
- Knuth TAOCP Vol.3 §5.2.1
- Shell 1959 CACM 2(7)
- Peters 2002 Timsort CPython

*The Codex Coding — thecodex.expert/coding/ — Free forever*