Instructions: DO NOT WRITE PROGRAMS. Write in pseudocode or explain your algorithm in words $($the latter is preferred$).$ For all lgorithms, always explain precisely why they work. Do not simply answer "yes" or $"$no$"$ to questions; you must justify your answers.

ALWAYS analyze the running time complexity of your algorithms. Strive to achieve the fastest possible running time for all algorithms. A correct algorithm with slow running time may not receive full credit.

Question $1$: Suppose we are given an unsorted array. Let $s(i)$ be the index of $A[i]$ in the sorted array, with the index starting at $1.$ Define distance $(i)=|s(i)-i|.$ Provide an algorithm that sorts the elements, assuming that distance $(i)20$ for every $i.$

Example: Given the unsorted array $4,1,3,2,6,5$ : In the sorted array $1,2,3,4,5,6,$ the index of $4$ is $4($originally at index $1),$ so $s(1)=4.$ Thus, distance $(1)=|4-1|=3.$