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:

1. unsigned int aux[m];
2. aux[vec[i]] = i;
3. 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.