Insertion sort is one of the first few algorithms that you would come across when learning about sorting algorithms. It is an easy to understand sorting algorithm that helps to build the foundation of sorting logic. However, it is not as efficient as some of the other algorithms as the worst-case complexity of Insertion Sort is O(n²).
Lets see how this algorithm works:
- Given an unsorted array with n elements
arr = [3, 4, 7, 5, 6, 2, 1]
- We skip the first element as it makes no sense to compare it with itself.