Insertion sort

Insertion sort is an 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" and the other elements are called "unsorted". Then, we look for the first "unsorted" element. If the first "unsorted" element is not bigger than the rightmost "sorted" elements, the algorithm just swaps downward that element with the rightmost "sorted" 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
https://www.youtube.com/watch?v=OGzPmgsI-pQ