Insertion Sort
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 compared to more advanced algorithms such as Merge Sort and Quick Sort. It has a worst-case and average-case time complexity of O(n^2).