Insertion Sort
Build a sorted array one element at a time by inserting into position.
How it works
Insertion Sort builds the final sorted array one element at a time. It starts with the first element (trivially sorted) and iterates through the rest of the array. For each new element it scans left through the sorted region, shifting elements one position right until it finds the correct insertion point, then places the element there.
The algorithm mirrors how most people sort a hand of playing cards: you pick up a new card and slide it left past cards that are larger until it is in the right spot. This mental model makes Insertion Sort easy to reason about and implement correctly. It is adaptive — its inner loop terminates early when the element is already in place — giving O(n) performance on nearly-sorted input, far better than the O(n²) average case.
Insertion Sort is both stable and online: it can sort a list as it receives elements one at a time without needing to know the full input in advance. These properties, combined with excellent cache behaviour and tiny constant factors, make it the algorithm of choice for small n, and it is used as a base case inside Timsort and Introsort in many standard libraries.
Complexity
Visualizer
Where it's used in the real world
CPython / Java / V8 — Timsort
Sorting small runs within the larger merge-sort passTimsort (used in Python, Java Arrays.sort for objects, and V8) identifies natural runs in the data and uses Insertion Sort for runs shorter than ~64 elements. At this scale, Insertion Sort's cache-friendly sequential access and zero allocation overhead beat merge sort's divide-and-conquer bookkeeping.
C++ std::sort (libstdc++ Introsort)
Base-case sort for small subpartitionsGCC's std::sort switches from quicksort to Insertion Sort once a partition is ≤ 16 elements. The threshold is empirically tuned: below it, Insertion Sort's tight loop and in-place shifting outperform quicksort's pivot selection and recursion overhead.
Online streaming / real-time data ingestion
Maintaining a sorted buffer of incoming eventsBecause Insertion Sort is an online algorithm, it can process each new element as it arrives and slot it into the correct position in an already-sorted buffer in O(n) time without restarting. This is used in time-series event queues where events arrive nearly in order and the buffer must stay sorted for range queries.
Implementation
function insertionSort(arr: number[]): number[] {
const a = [...arr];
for (let i = 1; i < a.length; i++) {
const key = a[i];
let j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
return a;
}
// Usage
console.log(insertionSort([38, 27, 43, 3, 9, 82, 10, 55]));
// [3, 9, 10, 27, 38, 43, 55, 82]