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.