Smallest possible sorting network for given permutation
For concreteness, let us assume that $x_1,\ldots,x_n$ are numbers between $1$ and $n$, and that a comparison puts the smaller number at the smaller index.

Consider first the case in which $n$ is even. We divide $x_1,\ldots,x_n$ into two halves: $x_1,\ldots,x_{n/2}$ and $x_{n/2+1},\ldots,x_n$. Let us call a number misplaced if it is in the wrong half: that is, a number in the first half is misplaced if it is in $\{n/2+1,\ldots,n\}$, and a number in the second half is misplaced if it is in $\{1,\ldots,n/2\}$. Note that the first half contains as many misplaced numbers as the second half (why?). Using one round of parallel comparisons, you can exchange the locations of the misplaced numbers, and guarantee that $\{x_1,\ldots,x_{n/2}\} = \{1,\ldots,n/2\}$, and similarly $\{x_{n/2+1},\ldots,x_n\} = \{n/2+1,\ldots,n\}$. Now recursively sort each half, in parallel.

When $n&gt;1$ is odd, we use the same strategy, dividing the array into two unequal halves, say the first half larger than the second by one element.

As an illustration, suppose that we are given the array
$$3,4,2,6,1,5$$
We switch $1$ and $4$ to obtain
$$3,1,2,6,4,5$$
Now we recursively sort $3,1,2$ and $6,4,5$.

In order to sort $3,1,2$, we first exchange $1$ and $3$ to obtain $1,3,2$, and then sort the two halves $1$ and $3,2$ in parallel, which means to exchange $2$ and $3$.

Sorting $6,4,5$ is completely analogous.