# 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

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.

• Can you give an example of such a list you want to sort? I dont understand if the $k$'th element is considered the $k$'th largest number, or the $k$'th element is literally the $k$'th new element you see when you scan the array from left to right. For example, is $[4,2,2,5,5,5,5,1,1,1,1,1,1,1,1]$ an example of such an array, or is $[4,4,4,4,2,2,5,5,5,5,5,5,5,5,1]$ an example of such an array? – nir shahar Apr 25 at 9:38

## 1 Answer

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)$$.