Algorithm to "scale" an array in place Problem: transform an array $A$ of $n$ natural numbers (of $t$-bits) into an array $B$, which is a permutation of $\{1, ..., n\}$ with the property that, whenever $B[i] \leq B[j]$ holds, $A[i] \leq A[j]$ holds. Call this operation "scaling".

For instance:

A = 7 7 2 5 9
B = 3 4 1 2 5
B = 4 3 1 2 5 -- a second "non stable" possibility


Assuming $n$ can be represented in $t$ bits, is there a way of scaling an array in place?

The time and space complexity should be as close to $O(n)$ and $O(1)$ as possible, with a $O(\log n)$ factor being probably acceptable.

A. Maus, IPS, sorting by transforming an array into its own sorting
permutation with almost no space overhead, solves a related problem; but it seems that the method approaches standard bucket sorting, requiring $O(n)$ space, as $\log_2 n$ approaches $t$.
Correct me if I'm wrong, but given this is possible with O(n) time, then you can build the sorted array in O(n) time, too:

for(i=0; i&lt;n; i++) {
 C[P[i]] = A[i];
}


If so, there's no way this can be done in O(n), since sorting is O(n.log(n)) at least.
When you take that into account, there are many O(n.log(n)) sorting algorithms, that can be easily fitted for your purpose and you can implement it this way:

B = array(1..n);
sort(B, cmp_func);


where cmp_func(int a, int b) compares A[a] and A[b] instead of a and b.

Sorry for my lame pseudocode, but I think it's understandable.