Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the sorted array one element at a time by repeatedly taking the next element and inserting it into its correct position in the already sorted portion.