$(25$ points$)$ Consider an array of integers that is $k-$almost sorted. By $k-$almost sorted, we refer

to the situation where the index of any element can be at most $k$ indices away from its correct

index as per ascending order. For instance, the array

is $3-$almost sorted because every element is at most $3$ positions away from its correct index.

Write an algorithm that takes as input $A,$ the valuation $k$ and returns a sorted array. Derive

the runtime of your algorithm.