Insertion sort

Insertion sort is a in-place sorting algorithm that goes one element at a time.

In the insertion sort algorithm, we call the first element of the array "sorted". Then, we look for the next element. If the next element is not bigger than the current element, the algorithm just shifts downward that element before the current element until it is in the right position and mark it as "sorted", and so on.

To implement the insertion sort algorithm efficiently, the array should implemented using a linked list.

The worst-case scenario is when that algorithm is used on a reverse ordered array. Each element should be shifted to other side of the array. The complexity is O(n²).

The best-case scenario is when the algorithm is used on a sorted array. There is O(n) comparisons.

Resources

https://www.youtube.com/watch?v=kU9M51eKSX8