$(25$ pts$)$ Consider the Deviation Sorting Problem:

Input: An array $A=($:$a_1,a_2,$dots,$a_n$:$)$ of $n$ numbers.

Output: The sorted absolute deviations $($in nondecreasing order$)$ of the numbers from the array average.

Ex: Let $A=($:$3,5,8,10,9$:$),$ then the array average $\frac{?}{\text{b}\text{a}\text{r}}(A)=\frac{3+5+8+10+9}{5}=7.$ The absolute deviation $d_i$ of $a_i$ from the array average $\frac{?}{\text{b}\text{a}\text{r}}(A)$ can be calculated as $d_i=|a_i-(\frac{?}{\text{b}\text{a}\text{r}}(A))|.$

Then, the unsorted absolute deviations array can be given as $D=($:$4,2,1,3,2$:$).$

We obtain the output as $($:$1,2,2,3,4$:$)$ after sorting the array $D$ in nondecreasing order.

a$.(10$ pts$)$ Design an algorithm, say Deviation Sorting algorithm, that solves Deviation Sorting Problem. Give the pseudocode of your algorithm. $($Hint: You may use a sorting algorithm from the lecture.$)$

b$.(7$ pts$)$ Show the iterations step$-$by$-$step of your algorithm on the instance in the example.

c$.(8$ pts$)$ What is the computational complexity of your algorithm? Is it an efficient algorithm or not? Discuss in detail.