Insertion Sort

overview

Summary

insertion_sort is a simple comparison sort. It builds a sorted left portion by inserting each new key into its correct place via shifts. It is in_place with space_complexity O(1). time_complexity: best O(n) on nearly sorted input, average O(n^2), worst O(n^2). It is a stable_sort and adaptive, good for small or nearly sorted arrays. Common uses: teaching, small datasets, and as a base case in hybrid sorts. Steps: pick key, compare, shift larger elements, insert.