Insertion sort iterates through an array, comparing each element with its neighbor and swapping them if they are in the wrong order.

Mark first element as sorted

for each unsorted element X

for j=0 lastSortedIndex down to 0

if current element > x, move

break loop and insert X