Inserion Sort

Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one element at a time. It’s like sorting a hand of playing cards—each time you pick a card, you place it in its correct position relative to the cards already in hand.

How it Works:

1->Start with the second element (since a single element is trivially "sorted").

2->Compare it to the element before it.

3->If the second element is smaller, shift the first element to the right to make space.

4->Continue comparing the second element to the elements before it, shifting them to the right, until the second element is in its correct position.

5->Move to the next element and repeat the process until the entire array is sorted.