様々な解法がありますが、その \(1\) つを紹介します。

\(k=N,N-1,\ldots,5\) の順で着目します。 \(k\) を \(k\) 番目に持っていくために \(k\) を右に動かすようなスワップだけを選んで行うことにします。はじめにパリティがあっていないならば、(\(k\) に影響を与えないような)どこかで適当にスワップを1回行い、(\(k \geq 5\) より \(k\) 番目以降に影響を与えないような位置が存在する)その後はスワップを繰り返して \(k\) 番目に動かせばよいです。

\(k=4\) もほぼ同様ですが、\((1,3,4,2,\ldots)\) などで次が偶数回目の場合必ず操作の対象になってしまいます。この場合場合も \(2 \rightarrow 3 \rightarrow 2 \rightarrow 3\) を \(i\) として指定してスワップを実行すればよいです。

残った \(3\) つについては、交互に操作を行い続けると以下のように昇順に並び替えることができます。 \((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)\)

このアルゴリズムは \(\frac{N(N+1)}{2}\) 回程度のスワップで動作します。実際に実行すると \(N=2,3,4\) の場合も \(N^2\) 回以下で動作するため、正解することができます。