This blog is inspired by problem 1591D - Yet Another Sorting Problem, hope you will enjoy it.
Basic concepts
First of all, let's define some basic things, you can skip it if you know it.
Parity of permutation $$$p$$$ is parity of number of inversions in it. Inversion is pair $$$(i, j)$$$ such that $$$i < j, p_i > p_j$$$.
Composition of permutations defined as follows $$$(f \circ g)_x = f_{g_x}$$$, we first apply $$$g$$$, then $$$f$$$.
Cycle is a permutation, where some indices are cyclic shifted, for example $$$p = \begin{pmatrix}1 & 5 & 2 & 4 & 3\end{pmatrix}$$$ is a cycle $$$\begin{pmatrix}2 & 3 & 5\end{pmatrix}$$$.
Theorem. Every permutation is composition of non-intersecting cycles.
Proof. Consider directed graph where vertices are numbers from $$$1$$$ to $$$n$$$, and edges are $$$i \to p_i$$$ for all $$$i$$$. Since $$$p$$$ is permutation, indegree and outdegree of each vertex is 1, hence our graph is collection of cycles, that's what we want.
Lemma. Applying swap to permutation will change its parity.
This lemma is very important, so it is left to reader as an exercise.
Fact. Parity of $$$(f \circ g)$$$ is sum of parities of $$$f$$$ and $$$g$$$.
Proof. Applying swap to permutation change its parity, thus if permutation $$$f$$$ can be represented as $$$k$$$ swaps, then parity of $$$k$$$ is parity of $$$f$$$. So if $$$f$$$ can be represented as $$$k$$$ swaps, and $$$g$$$ can be represented as $$$m$$$ swaps, then $$$f \circ g$$$ can be represented as $$$k + m$$$ swaps, but parity of $$$f \circ g$$$ is parity of $$$k + m$$$, which is sum of parities of $$$f$$$ and $$$g$$$, QED.
Counting inversions, parity of permutation
There are many ways to count number of inversions in $$$O(n \log n)$$$ time.
But there is a simple way to count parity of permutation, without directly counting number of inversions.
Theorem. Permutation can be represented as composition of 3-cycles if and only if it is even.
Proof. 3-cycle is even, so composition of 3-cycles must be even, so all that we need to do is proof, that for any even permutation exists such representation.
We will try to build our permutation from identical applying 3-cycles. On $$$i$$$-th iteration we assume, that first $$$i - 1$$$ elements of permutation are in place, and we will try to place $$$i$$$-th element. If $$$i$$$-th element is not in place, then now in current permutation it is on $$$j$$$-th place, $$$j > i$$$. Let's do cycle $$$n \to j \to i$$$, if $$$j \neq n$$$, and if $$$j = n$$$, do $$$n - 1 \to j \to i$$$, so we won't corrupt first $$$i - 1$$$ elements, and we will place $$$i$$$-th element.
So we can do $$$n - 2$$$ steps. After that there are two possible situations.
$$$n - 1$$$-th and $$$n$$$-th elements are in place, this means that we represented our permutation as 3-cycles, so our permutation is even and we've found representation for it.
They are not in place, they are swapped. Because on each step of algorithm permutation is even, and it differs from our permutation by one swap, thus our permutation is odd, so it can't be represented.
So we've proven this theorem and got $$$O(n)$$$ algorithm with good constant, which can be useful in other problems involving parity of permutation.
