# Insertion Sort visualised: card sorting in O(n^2)

> Interactive Insertion Sort: builds a sorted prefix on the left and shifts each new element into its slot. Linear best case, quadratic worst case, stable.

Address: https://marckimmel.de/en/informatik/sortieralgorithmen/insertion-sort
Deutsche Fassung: https://marckimmel.de/informatik/sortieralgorithmen/insertion-sort.md

Grows a sorted prefix on the left and inserts each new element into the right slot.

Insertion Sort treats the array like a deck of cards: the sorted prefix lives on the left, the unsorted tail on the right. In every step it picks the first unsorted element (the key) and compares it from right to left with all values in the sorted prefix. As long as a value is larger than the key, that value is shifted one position to the right. As soon as a smaller value (or the array start) is found, the key is placed into the resulting gap. The sorted prefix grows by one each iteration. The best case is an already-sorted input where the inner check exits immediately, giving linear best-case runtime O(n). In the average and worst case each element may compare and shift against i predecessors, leading to quadratic total runtime O(n^2). Insertion Sort runs in-place and uses only constant extra memory O(1). Equal elements keep their order, so the algorithm is stable.

Very strong on small arrays with fewer than roughly 20 elements and on nearly sorted data, where the runtime drops to linear. That is why hybrid sorts like Timsort fall back to Insertion Sort once the recursive sub-ranges are small enough.

## Related

- [Sorting Algorithms](https://marckimmel.de/en/informatik/sortieralgorithmen.md)