NOTE
Insertion Sort
Stable in-place insertion into a sorted prefix, efficient for small or nearly sorted inputs.
This is a historical learning note and may contain outdated or incomplete understanding.
Insertion sort maintains a sorted prefix and inserts each next element into its correct position by shifting larger elements.
Worst/average time is O(n^2), but nearly sorted input can approach linear work. It is in-place and can be stable.
Because constants are low, tuned sorting implementations often use insertion sort for small partitions even when the overall algorithm is O(n log n).