0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – nir shahar Apr 25 at 9:38
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.