Insertion Sort

Grow a sorted prefix one element at a time. For each new value, slide it leftward past any larger neighbors until it drops into the right slot. It mutates in place and only ever compares adjacent items.

Small arrays (roughly n ≤ 16) and data that is already mostly sorted — it runs in O(n) on presorted input. TimSort, Java's Arrays.sort, and many library sorts fall back to it for short runs for exactly this reason.

Arrays longer than a few dozen elements with random order. The O(n²) shifting cost blows up fast, and the linear-memory access pattern doesn't save you past that threshold.