Insertion Sort

Insertion sort is a simple sorting algorithm that works by iteratively building a sorted sub-array from left to right. The idea behind insertion sort is to take one element at a time and insert it into its correct position in the already sorted sub-array to its left.

Here's how insertion sort works:

1. We start with the first element of the array as our initially sorted sub-array.
2. For each element in the unsorted part of the array, we compare it to the elements in the sorted sub-array from right to left until we find the correct position for the element.
3. Once we have found the correct position, we insert the element into the sorted sub-array at that position.
4. We repeat this process until all elements in the unsorted part of the array have been inserted into the sorted sub-array.

This process is repeated until the entire array is sorted. Insertion sort has a worst-case time complexity of O(n^2), but in practice, it is often faster than other algorithms for small arrays or nearly sorted arrays.