Insertion Sort

Insertion sort sorts a list by repeatedly inserting each item into its correct position within a growing sorted portion. It’s simple and efficient for small or nearly sorted lists.