# Sorting geometric array in linear time without finding majority element

It's an exercise I was given:
We say array of numbers $A$ is geometric if:

• It has size $n=2^k-1$
• It has $\log n$ distinct numbers
• For each $0\leq i \leq k-1$ there exists an element in the array that appears exactly $2^i$ times.

For example: $[8,5,2,5,5,5,8], k=3$
I need to sort the array in $\mathcal{O}(n)$ time and space.
I can solve it by using any algorithm that finds majority element in linear time.
My question is, can we solve it without finding using algorithm that finds majority element?

• counting sort is the obvious answer. – ratchet freak Sep 8 '17 at 13:54
• Can you elaborate please? – sel Sep 8 '17 at 14:00
• en.wikipedia.org/wiki/Counting_sort – ratchet freak Sep 8 '17 at 14:05
• If they are integers then count sort. Unless the range is bigger than n it will be O(n) space. – paparazzo Sep 8 '17 at 14:45
• We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Sep 8 '17 at 20:46