Insertion sort

Insertion sort maintains the sorted part of the array at the beginning of the array. For ith element, arr[0..i-1] is sorted; we then search for the position where arr[i] belongs, insert it at that position, and shift the affected elements to right.

Red-colored elements are to the right of where current elements (white) are supposed to be inserted, we move all red elements to the right by one place.