# Insertion Sort — Intuitive Stable Sort (C++) ## Overview Insertion sort builds a sorted prefix by inserting the next element into its correct position. It is simple, stable, and performs well on small or nearly-sorted arrays. ## Complexity - Worst-case: **O(n^2)** - Best-case (already sorted): **O(n)** - Space: **O(1)** (in-place) ## Implementation notes (repo) See `insertion.cpp` for a straightforward `for` loop shifting elements to insert the key. ### Core idea ```cpp\nfor (int i = 1; i < n; ++i) { int key = a[i]; int j = i-1; while (j >= 0 && a[j]> key) { a[j+1]= a[j]; --j; } a[j+1]= key; }\n``` ## Use cases - Small arrays (n < ~50) - Adaptive: very fast if input is nearly sorted ## Source `https: //github.com/mashrur-rahman-fahim/algorithm/blob/main/insertion.cpp`.