sorting algorithm in O(n) according a specific condition

Given an array A with n−1 numbers where n = 2k
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 Θ(n), and analyze its running time.
example: input: 5,1,2,1,2,2,2
output: 1,1,2,2,2,2,5


some important pointers:
1.the time comlexity should be Worst case
2.using a dictionary is not allowed
3.the solution should use a stack or other basic data structures


i tried using counting sort but it didnt work because the array doesnt contain values starting from 0 and up.
i also thought about using a hash map but the wanred time complexity would be expected and not worst case.
thanks for the help in advance