Sort vector<int>(n) in O(n) time using O(m) space?
- by Adam
I have a vector<unsigned int> vec of size n. Each element in vec is in the range [0, m], no duplicates, and I want to sort vec. Is it possible to do better than O(n log n) time if you're allowed to use O(m) space? In the average case m is much larger than n, in the worst case m == n.
Ideally I want something O(n).
I get the feeling that there's a bucket sort-ish way to do this:
unsigned int aux[m];
aux[vec[i]] = i;
Somehow extract the permutation and permute vec.
I'm stuck on how to do 3.
In my application m is on the order of 16k. However this sort is in the inner loops and accounts for a significant portion of my runtime.
