How can I find the inverse of a permutation? My question is, how can the inverse of $5 9 1 8 2 6 4 7 3$ be $3 5 9 7 1 6 8 4 2$? At first glance, 1 and 2 are both less than 3, for example, which seems to conflict with the instruction "then sorting the columns into increasing order". Is  this not a total order over the natural numbers?

The reader should not confuse inversions of a permutation with the inverse of a permutation. Recall that we can write a permutation in two-line form
$$\left(\begin{matrix} 
  1 & 2 & 3 & \cdots & n\\
  a_1 & a_2 & a_3 & \cdots & a_n
  \end{matrix}\right)$$
the inverse $a'^1a'^2a'^3 ... a'^n$ of this permutation is the permutation obtained by interchanging the two rows and then sorting the columns into increasing order of the new top row:
$$\left(\begin{matrix} 
  a_1 & a_2 & a_3 & \cdots & n\\
  1 & 2 & 3 & \cdots & n
  \end{matrix}\right)=\left(\begin{matrix} 
  1 & 2 & 3 & \cdots & n\\
  a'_1 & a'_2 & a'_3 & \cdots & a'_n
  \end{matrix}\right) $$
For example, the inverse of $5 9 1 8 2 6 4 7 3$ is $3 5 9 7 1 6 8 4 2$, since
$$\left(\begin{matrix} 
  5 & 9 & 1 & 8 & 2 & 6 & 4 & 7 & 3\\
  1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9
  \end{matrix}\right)=\left(\begin{matrix} 
  1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
  3 & 5 & 9 & 7 &1 & 6 & 8 & 4 & 2
  \end{matrix}\right) $$

— Knuth, Donald. The Art of Computer Programming: Sorting and Searching. Vol. 3, Second Edition.
 A: Given permutation is: 591826473
To get the inverse of this  first write down the position of 1
It is in the 3rd position . SO inverse starts as "3 ...". Next locate 2 in the permutation. It is in the 5th position. So inverse expands to "35...." Similarly go on chasing 3,4 etc and note down their positions and build the inverse permutation.
A: The last step is to sort the columns $j\choose i_j$ in increasing order such that the column $1\choose i_1$ comes first, then comes $2\choose i_2$ and so on. Indeed, the wording is a bit misleading. The column $j\choose i_j$ stands for the assignment $j\mapsto i_j$ (here in the inverse permutation).
A: For some general theory see
$\quad$ Converse relation of a function
Let $\bar 9 = \{1,2,3,4,5,6,7,8,9\}$ and observe that this set comes equipped with a natural ordering.
The permutation $\rho = | \;5\,9\,1\,8\,2\,6\,4\,7\,3 \; |$ in $S_9$, by definition (compact notation), has graph
$\quad G_{\rho} = \{\,(n, n^{th} \text{ spot in } | \; 5\,9\,1\,8\,2\,6\,4\,7\,3 \; |) \mid n \in \bar 9 \, \} $
Also, $\rho^{-1} = {G_{\rho}}^{-1}$.
Since $1$ is in spot $3$ of $| \;5\,9\,1\,8\,2\,6\,4\,7\,3 \; |$, $\; \rho^{-1} = | \;3\,?\,?\,?\,?\,?\,?\,?\,? \; |$;
Since $2$ is in spot $5$ of $| \;5\,9\,1\,8\,2\,6\,4\,7\,3 \; |$, $\; \rho^{-1} = | \;3\,5\,?\,?\,?\,?\,?\,?\,? \; |$;
$\dots$
Since $9$ is in spot $2$ of $| \;5\,9\,1\,8\,2\,6\,4\,7\,3 \; |$, $\; \rho^{-1} = | \;3\,5\,9\,7\,1\,6\,8\,4\,2 \; |$ and done.
