Insertion sort on shrinking gaps — breaks up the O(n²) wall.
Run insertion sort on elements spaced a large "gap" apart, then shrink the gap and repeat. Early passes move items long distances cheaply, and the final gap-1 pass is a nearly-sorted insertion sort — which is the case where insertion sort excels.
Medium arrays (thousands of elements) on memory-constrained systems. In-place, no recursion, no auxiliary buffer — a solid middle ground when you can't afford mergesort's O(n) working space.
You need a tight theoretical worst-case bound. Performance depends heavily on the gap sequence, and the analysis is famously messy; reach for heapsort when guarantees matter.