Insertion Sort: It builds the final sorted array one item at a time. It iterates through the input array and for each element, it finds the correct position within the already sorted portion of the array and inserts it there. Elements greater than the current element are shifted one position to the right.
Color Legend: