# How to prove cycle sort has the minimum swap times?

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.

• Before we can prove a theorem, we need a precise formulation of it. What is the computation model? What exactly are we counting? Mar 14, 2022 at 11:16
• Based on th description of the algorithm in the Wikipedia article you gave, the algorithm moves an element once, to its correct position, if needed. If this movement requires displacing another element, this other element is the next element to be relocated to its right position. This is repeated until all elements are in place. Mar 14, 2022 at 11:23
• Wikipedia contains a complete proof of minimality: "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." Mar 14, 2022 at 11:46
• You could also come up with an algorithm that minimizes the number of swaps, though this seems to be different from the algorithm described by Wikipedia. The minimum number of swaps is $n$ minus the number of cycles (where $n$ is the length of the array). This is minimal since it's the same as the number of transpositions which multiplies to the permutation, and every transposition reduces the number of cycles by at most 1. Mar 14, 2022 at 11:47
• Please don't use "Edited:". There is no need to mark what has changed. Instead, revise the question so it reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. If you asked the wrong question, and realize this after you have already received an answer to the wrong question, then please don't change the question after the fact. Instead, it is better to ask a new question, and make the new question self-contained.
– D.W.
Mar 15, 2022 at 20:16

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.