There are many possible solutions. Here, we will describe one of them.

Let us focus on \(k=N,N-1,\ldots,5\) in this order. To bring \(k\) to the \(k\)-th position, let us only do swaps that move \(k\) to the right. If the parity is not matched in the beginning, we will do a swap somewhere that does not affect \(k\) (since \(k \geq 5\), there is such a position). Then, we can repeatedly do swaps to move \(k\) to the \(k\)-th position.

We can use similar tactics on \(k=4\), but if we have \((1,3,4,2,\ldots)\) and the next swap is even-numbered, for example, not affecting \(k\) is impossible. In such a case, we will do swaps choosing \(2 \rightarrow 3 \rightarrow 2 \rightarrow 3\) as \(i\).

For the remaining three, we can sort them in ascending order by alternating between the two operations, as follows: \((1,2,3) \rightarrow (2,1,3) \rightarrow (2,3,1) \rightarrow (3,2,1) \rightarrow (3,1,2) \rightarrow (1,3,2) \rightarrow (1,2,3)\)

This algorithm works in approximately \(\frac{N(N+1)}{2}\) swaps. It turns out that it also handles the case \(N=2,3,4\) in not more than \(N^2\) swaps.