A simple sorting algorithm that builds the final sorted array one item at a time by inserting each element into its correct position.
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: it is simple to implement, efficient for small data sets, adaptive (efficient for data sets that are already substantially sorted), stable (does not change the relative order of elements with equal keys), in-place (only requires O(1) additional memory space), and online (can sort a list as it receives it).