Problem
I need to design an algorithm that takes a list of integers as an input and returns a sorted list of the elements greater than the first log(n) and smaller than the last n - 3 log(n) (in other words, I need a sorted list of 2log(n) elements). The integers of the array are between 0 and 2^n. They must be sorted in linear time O(n), where n is the number of elements in the entire list. The fact that we only need a subset of the elements sorted might be relevant to finding a solution but I haven't found its relationship.
My solutions
I have tried two solutions.
- Using counting sort, but that yields and exponential (
2^n) time and space complexity - Using radix sort, but that yields a quadratic time complexity. This is due to the fact that
T(n) = O(d*(n + b)) = O(log_b(2^n)*(n + b)) = O(n * log_b(2) * (n + b)) = O(n^2)independently of the value of b.
As you can see I am a little lost into what to try next. Thanks in advance!