I've started with thinking of a bucket sort/radix sort variation, only to be disproved by a colleague.
Here's the problem:
Given an array with $k$ distinct elements, it is known that the smallest element appears once, the 2nd smallest element appears twice, the 3rd smallest element appears 4 times, the 4th smallest appears 8 times, and so on until the $k$-th smallest element, which appears exactly $2^{k-1}$ times.
Marking the size of the array as $n=2^k-1$, suggest an algorithm to stable sort the array in $O(n)$, provide explanation for the algorithm.
The second path of thought I had was making a new array sized $\log(n)$ with a queue in each cell, thus repeating elements keep their order.
However, the best algorithm I came of is doing this is $O(nk)=O(n\log n)$ time, which seems pretty legit to a sorting algorithm without a given range(such as in bucketsort). Yet the problem demands $O(n)$.