Sorting an array where the largest element appears once, the second largest appears twice and in general the $k$-th element appears $2^{k-1}$ times

Question

I need to find a sorting algorithm to sort an array where the the $k$-th element appears $2^{k-1}$ times in $O(2^k)$.

It also given there are $k$ distinct elements in the array, hence there are $1 + 2 + 2^2 + \dots + 2^{k-1}=2^k-1$ elements in the array. So I actually need to sort the array in $O(n)$ where $n$ is the array size.

Not sure how to use the known quantity of each element to sort faster.

Any help is appreciated.

Answer 1

If I understand correctly the title (which is a bit clearer than the post itself), an example of such an array would be $[1, 4, 1, 2, 1, 2, 5, 2, 1, 1, 4, 1, 2, 1, 1]$.

If that's the case, you can:

• Count the number of occurrences of each value, with a hashtable for example;
• Sort the unique values with descending order of occurrences;
• Recreate the sorted array by repeating each value by the number of occurrences.

This algorithm is indeed in time complexity $O(n)$, since the array contains only $\log_2 (n+1)$ unique values. That means that even the worst case of operations in the hashtable is in complexity $O((\log n)^2)$, and sorting the unique values array can be done in $O(\log n \log \log n)$. The last step is done in $O(n)$.