Contest Duration: - (local time) (120 minutes) Back to Home

## C - Odd Even Sort Editorial by evima

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.

posted:
last update: