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 9B = 3 4 1 2 5B = 4 3 1 2 5 -- a second non stable possibilityAssuming $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 sortingpermutation 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$.
Algorithm to scale an array in place
ds.algorithms