How to prove cycle sort has the minimum swap times?

Question

Copy from Wikipedia

Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.

Why does cycle sort have minimum write times (or minimum swap times)? I can't find such a claim in the paper Cycle-Sort: A Linear Sorting Method. I have met different variants of cyclesort, so I want to know the specific proof method.

Edited: I misunderstood minimum write times with minimum swap times, so the premise of the problem is wrong.

Answer 1

Cycle sort minimizes the number of times that a value is written to the array, as proved in the Wikipedia article:

Each value is either written zero times, if it's already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.

Another implementation of cycle sort only uses swaps. Sorting a cycle of length $\ell$ requires $\ell-1$ swaps (this includes the special case of a fixed point, in which $\ell=1$), for a total of $n-c$ swaps, where $c$ is the number of cycles. This is optimal. Indeed, denote the initial permutation of the array by $\pi$, and the swaps applied to it by $\sigma_1,\ldots,\sigma_m$. Thus $$ \sigma_m \cdots \sigma_1 \pi = \mathsf{id}, $$ implying that $\pi = \sigma_1 \cdots \sigma_m$. It remains to show that if we write $\pi$ as a product of transpositions, then there at least $n-c$ transpositions in the product. Indeed, since the identity permutation has $n$ cycles and multiplying by a transposition reduces the number of cycles by at most $1$, any such product must contain at least $n-c$ transpositions.