Whoname and Unsorted Array

The operation becomes much less cursed if we give names to its four pieces. Suppose the selected pair is $(x,y)$ and the array is

$$[A,x,y,B].$$

One operation transforms it into

$$[x,A,B,y].$$

So $x$ goes to the front, $y$ goes to the back, and every unselected element keeps its relative order. That last fact drives the entire construction.

Which permutations are impossible?

Moving $x$ across $A$ takes $i-1$ adjacent swaps. Moving $y$ across $B$ takes $n-i-1$ adjacent swaps. Therefore one operation has the same parity as

$$(i-1)+(n-i-1)=n-2$$

adjacent swaps. Its sign is consequently

$$(-1)^{n-2}=(-1)^n.$$

• If $n$ is even, every operation is even. The identity permutation is even, so an odd initial permutation can never reach it.
• If $n$ is odd, every operation is odd. Parity places no restriction on the starting permutation.

Parity alone does not prove that every remaining case works. The construction below does that.

We can compute the initial parity by counting inversions modulo $2$. With $\sum n\le 5000$, the direct $O(n^2)$ loop is entirely fine. A Fenwick tree here would mostly be algorithmic cosplay.

Build a deliberately misplaced suffix

We process $k=1,2,\ldots,n-2$. Before processing $k$, maintain the invariant that the array ends with

$$S=[1,2,\ldots,k-1].$$

This suffix is increasing, but it is not yet sitting in its final positions. That is intentional. Since an operation can append its second selected element while preserving $S$, increasing values from $1$ upward is the convenient direction.

All values from $k$ through $n$ are somewhere before $S$.

Case 1: $k$ is not first

Let $x$ be the element immediately before $k$. The array has the form

$$[A,x,k,B,S].$$

Choose the pair $(x,k)$. The operation produces

$$[x,A,B,S,k].$$

Thus the new suffix is exactly

$$[1,2,\ldots,k-1,k].$$

This costs one operation.

Case 2: $k$ is first

Because we only process through $k=n-2$, at least three elements remain outside $S$. Hence the array can be written as

$$[k,a,b,R,S].$$

Perform operations at indices $2$, $1$, and $n-1$:

$$[k,a,b,R,S] \rightarrow [a,k,R,S,b] \rightarrow [a,R,S,b,k] \rightarrow [b,a,R,S,k].$$

Again, the suffix becomes $[1,2,\ldots,k]$. The prefix gets shuffled, but we genuinely do not care about its order yet.

Therefore every iteration extends the suffix using at most three operations.

Cleaning up the last two values

After processing $1$ through $n-2$, the array must be in one of two states:

$$A=[n-1,n,1,2,\ldots,n-2]$$

or

$$B=[n,n-1,1,2,\ldots,n-2].$$

For $n=2$, the only feasible permutation is already $[1,2]$, so we simply output zero operations.

State A

Use the indices

$$2,1,n-1,1.$$

The transformations are

$$[n-1,n,1,2,\ldots,n-2] \rightarrow [n,n-1,2,3,\ldots,n-2,1]$$ $$\rightarrow [n,2,3,\ldots,n-2,1,n-1] \rightarrow [1,n,2,3,\ldots,n-2,n-1] \rightarrow [1,2,\ldots,n].$$

So this state needs four more operations.

State B

State $B$ has

$$(n-1)+(n-2)=2n-3$$

inversions, which is odd. Therefore it cannot occur when $n$ is even and the input passed our parity check: every operation would preserve even parity.

It remains to handle odd $n$. First apply index $1$:

$$[n,n-1,1,2,\ldots,n-2] \rightarrow [n,1,2,3,\ldots,n-1].$$

Now apply index $2$ exactly $n-2$ times. An index-$2$ operation maps

$$[u,v,w,T]\rightarrow[v,u,T,w].$$

Thus each operation sends the next value among $2,3,\ldots,n-1$ to the back while swapping the leading pair $(n,1)$. Since $n$ is odd, $n-2$ is odd, so the result is

$$[1,n,2,3,\ldots,n-1].$$

One final operation at index $1$ gives the identity permutation.

This cleanup uses exactly $n$ operations.

Correctness proof

Lemma 1. If $n$ is even and the initial permutation has odd inversion parity, sorting is impossible.

Proof. Every operation is equivalent to $n-2$ adjacent swaps. For even $n$, this is even, so permutation parity never changes. The odd initial permutation therefore cannot become the even identity permutation. $\square$

Lemma 2. Before iteration $k$, if the suffix is $[1,2,\ldots,k-1]$, the algorithm extends it to $[1,2,\ldots,k]$ using at most three operations.

Proof. If $k$ has a predecessor, selecting that predecessor together with $k$ appends $k` while leaving the old suffix ordered. If$k$is first, the sequence of indices$(2,1,n-1)$transforms$[k,a,b,R,S]$into$[b,a,R,S,k]`. Both cases produce the required suffix. $\square$

Lemma 3. After the main loop, the cleanup sorts the permutation.

Proof. The first $n-2$ values form the suffix $[1,2,\ldots,n-2]$, so the first two values are $n-1,n$ in some order. The explicit four-operation sequence sorts state $A$. State $B$ cannot occur for feasible even $n$, while for odd $n$ the sequence consisting of $1$, then $n-2$ copies of $2$, then $1$ sorts it as shown above. $\square$

Theorem. The algorithm prints -1 exactly for impossible inputs and otherwise prints a valid sequence of at most $4n$ operations that sorts the permutation.

Proof. Lemma 1 proves every rejected case impossible. For every accepted case, repeatedly applying Lemma 2 reaches one of the two final states, and Lemma 3 sorts that state. Thus the produced sequence is valid. No other cases are rejected. $\square$

Operation bound

The main loop has $n-2$ iterations and uses at most three operations per iteration:

$$3(n-2).$$

State $A$ adds four operations, for at most $3n-2$. State $B$ adds $n$ operations, for at most

$$3(n-2)+n=4n-6.$$

Both satisfy the required $4n$ limit.

Complexity

We simulate every operation in $O(n)$ time and perform $O(n)$ operations. Finding each next value and checking parity also take $O(n^2)$ total time. Therefore:

$$\text{time}=O(n^2),\qquad \text{memory}=O(n).$$