Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by iterating through the input list and inserting each element into its correct position within the already sorted sublist to its left, much like how you might insert cards into a hand of playing cards.