Cfrgtkky

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.

The last step is to sort the columns $jchoose i_j$ in increasing order such that the column $1choose i_1$ comes first, then comes $2choose i_2$ and so on. Indeed, the wording is a bit misleading. The column $jchoose i_j$ stands for the assignment $jmapsto i_j$ (here in the inverse permutation).

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 "52...." Similarl go on chasing 3,4 etc and note down their positions and build the inverse permutation.