Insertion Sort
Builds a sorted prefix by inserting each new element into its correct position.
Stable:YesIn-place:Yes
Complexity
Best
O(n)
Average
O(n²)
Worst
O(n²)
Space
O(1)
When to use: Great for small arrays.SimpleSlow on large random inputs (O(n²) average/worst-case)
Pseudocode
for i from 1 to n-1: key = a[i]while j >= 0 and a[j] > keya[j+1] = a[j]a[j+1] = keydone
Waiting to start…