This question is aimed at cleaning up an implementation detail of an in-house sparse direct solver. It uses METIS to reorder $A$ into $PAP^{T}$ for reduced fill-in. Inside the $Lx=b$ and $L^{T}x=b$ backsolution routines, the solver needs to apply the same permutation matrix to $b$ upon entry, then undo the permutation on $x$ just before returning. This is currently done with a temporary vector $t$, by copying $b$ with permutation into $t$, performing the $L$ and $L^{T}$ backsolves in-place on $t$, then copying $t$ with permutation back into $x$. (actually $b$ and $x$ are aliases for each other, but there's still the $t$-temporary)
I would like to redo this operation to be completely in-place, eliminating the temporary $t$. I think that in order do so, I need to take the permutation vector as computed by METIS and determine a sequence of row swaps that yields it. (Is this correct?) The algorithm that I was thinking to implement would basically be like a customized quicksort with a customized comparator. (The comparator would be customized so that it will correctly sort $\{0, 1, 2 ,3,\ldots,N\}$ into METIS's answer, the quicksort would be customized to record the atomic swap operations so that they can later be applied in-place to $b$).
My question is - is this the best way to accomplish what I am trying to do? I can tell already that the answer (a sequence of row swaps to realize $P$) is non-unique, because any sorting algorithm will yield an answer, but might perform completely different swaps. For example, bubblesort vs. quicksort will obviously yield different sequences - one with $O(n^2)$ swaps, the other with $O(n \log n)$, but both would work. I think finding the minimum number of swaps would be better for performance, hence the bias towards $O(n \log n)$ sort algorithms, but is there a different approach that would be guaranteed to find a minimum length sequence of swaps? I would think there would be some way to find a sequence that was $O(n)$ in length.
