Implement the Insertion Sort algorithm for sorting an array of n elements. In this algorithm, the main loop index i runs from 1 to n-1. On the ith iteration, the element a[i] is "inserted" into its correct position among the subarray a[0..i]. This is done by shifting one position up all the elements in the subarray that are greater than a[i]. Then a[i] is copied into the gap between the elements that are less than or equal to a[i] and those that are greater.