Sorting Algorithms
quadratic · in place · stable

Watch <insertion sort> run.

The way you sort a hand of cards: lift the next one out, slide everything bigger to the right, drop it in the gap. The hatched bar is the slot you emptied — that value is in a variable, not in the array.

What it costs

Best case
O(n)Already sorted. Each value loses its first comparison and stays put — n−1 comparisons, zero shifts, and no flag needed to detect it.
Average
O(n²)Comparisons and shifts both track the number of inversions — pairs that start in the wrong order. That is what makes it fast on nearly-sorted input and slow on random input.
Worst case
O(n²)Reversed. Every value walks the whole sorted run: n(n−1)/2 comparisons and just as many shifts.
Extra memory
O(1)One variable holds the value in flight. Everything else moves within the array.
Stable
YesThe scan stops at the first value that is not strictly greater, so an equal value is never crossed. Loosen > to >= and stability goes.
Used in practice
YesReal sorts switch to it for small runs — roughly under 16 elements — because its constant factors beat quicksort and mergesort there. It is inside the standard library you already use.

Against bubble sort: same O(n²), but insertion sort writes only when something actually moves, while a bubble swap costs three writes each time. Run both on Nearly sorted to see the gap.