Insertion Sort

Insertion sort is a simple sorting algorithm that works by iterating over the elements of a list and inserting each element into its proper position in the sorted list. It is a comparison-based algorithm, meaning that it compares elements of the list to determine their order.The basic idea behind insertion sort is to iterate over the elements of the list one by one, and insert each element into its proper position in the sorted portion of the list. The sorted portion of the list is initially empty, and as the algorithm progresses, it grows to include more and more elements.