Editorial

Complete the columns from left to right. When processing column $i$ , consider its two target values, $i$ and $N+i$ , together. Never touch an already completed column.

If the two targets are in the same row, vertically swap the target that is in the wrong row at its current column. Both targets are now in their correct rows; move each left to column $i$ using horizontal swaps.
If the targets are in different rows, move each left to column $i$ within its current row. If their rows are reversed, finish with one vertical swap in column $i$ .

Store the current position of every value and update it after each swap. Record the swaps, then print their count and the recorded sequence. Both the time complexity and the space complexity, including the recorded swaps, are $O(N^2)$ .

Proof

Before column $i$ is processed, both targets are in columns $i$ through $N$ . All swaps remain within this region. The targets are placed in different rows before being moved left, so moving either target cannot displace the other. Thus column $i$ is completed correctly without disturbing earlier columns.

Let $m=N-i+1$ be the number of remaining columns. Each target needs at most horizontal swaps, and either case uses at most one vertical swap. The total number of swaps is therefore at most

Grid Sort

Editorial