Given an array A with n$1$ numbers where n $=2^$k

for some integer k$.$ One of the values appears exactly n$/2,$another appears exactly n$/4$ and so on$.$ More formally, for all $1<=$ k $<=$ log n exists a value that appears exactly n $/(2^$k$)$ times in the array. Describe an algorithm that sorts A with a run time complexity of $\backslash$Theta $($n$),$ and analyze its

running time.