Array with specific values

Question

Given an array the size of n where: 1/2 of the array is with a single (unknown) value. 1/4 of the array is with a single (unknown) different value. And so on for 1/8, 1/16, 1/32 Give an algorithm to sort the array. You cannot use the find median algorithm

So what I figured is: There are only logn different values There is a simple solution using a binary heap on O ( n*loglogn) It looks like a question that needed to be solved in O (n)

Answer 1

Here is one possible approach:

• scan the array and store element frequencies (there are log n distinct elements) in a hash table in amortized O(n) time; this is doable because we can do insertions in amortized O(1) time;
• now run a classic sorting algorithm on these log n elements: this is doable in deterministic O(log n log log n) time using, say, heap sort or merge sort;
• now expand the sorted array---or create a new one and fill it using the sorted array and the hash table---using frequencies from the hash table; this is doable in O(n) amortized time.

The whole algorithm thus runs in amortized O(n) time, i.e., it is dominated by eliminating duplicates and expanding the sorted array. The space complexity is O(n).

This is essentially optimal because you need to "touch" all the elements to print the sorted array, which means we have a matching lower bound of Omega(n) on the running time.

Answer 2

The idea is to use the Majority algorithm that takes O(n) then discovering what's the "half" value deleting it from the array and then doing it again on the new array n+n/2+n/4+n/8+..... < 2n => O (n)