Insertion Sort

Insertion sort: Build sorted array by inserting each element into correct position.

Left portion sorted. Take next unsorted element. Shift larger elements right. Insert.

Example $[5,2,4,6,1,3]$: $1.$ $[5]$ sorted. Insert $2$: $[2,5]$

$2.$ Insert $4$: $[2,4,5]$

$3.$ Insert $6$: $[2,4,5,6]$

$4.$ Insert $1$: $[1,2,4,5,6]$

$5.$ Insert $3$: $[1,2,3,4,5,6]$

Time: $O(n^2)$ worst, $O(n)$ nearly sorted.