Algorithm to "scale" an array in place
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.