How to sort an array according to another array?

Construct an index array:

i = { 0, 1, 2, 3 }

Now, while you are sorting p, make the same changes to the index array i.

When you're done, you'll have:

i = { 1, 3, 0, 2 }

Sorting two arrays takes at most twice as long as sorting one (and actually, if you're only counting comparisons you don't have to do any additional comparisons, just data swaps in two arrays instead of one), so that doesn't change the Big-O complexity of the overall sort because O( 2n log n ) = O(n log n).

Now, you can use those indices to construct the sorted A array in linear time by simply iterating through the sorted index array and looking up the element of A at that index. This takes O( n ) time.

The runtime complexity of your overall algorithm is at worst: O( n + 2n log n ) = O( n log n )

Of course you can also skip index array entirely and simply treat the array A in the same way, sorting it along side p.